接雨水
解法一
暴力(按列求)
获取离当前节点最远左右两边比当前节点值大的值height[l],hright[r]
因为决定装水容量的是矮的所以取height[l],hright[r] 中小的那个减去height[i]就是当前节点可以存放的水，然后遍历
class Solution { public int trap(int[] height) { int res = 0; int len = height.length; for(int i = 0;i < len;i++){ int left = i -1; int right = i+1; int maxl = i; int maxr = i; // 找到离当前节点最远的左边比当前节点值大的值 while(left >= 0){ if(height[left] > height[maxl]){ maxl = left; } left--; } //找到离当前节点最远的右边比当前节点值大的值 while(right < len){ if(height[right] > height[maxr]){ maxr = right; } right++; } if(maxl != maxr){ res = res + Math.min(height[maxl],height[maxr]) - height[i]; } } return res; } }
解法二(按行求)
暴力(按行求)
先取得最高高度mH
然后分别求取1~mH行的雨水
每次遍历height数组，如果当前height[i] < nowH(当前行)并且左右两边都有大等于的nowH的那么就可以res++
class Solution { public int trap(int[] height) { int res = 0; int len = height.length; int mH = 0; //保存最大高度 for(int i = 0;i < len;i++){ mH = Math.max(height[i],mH); } for(int i = 1;i <=mH;i++){ for(int j = 1;j < len-1;j++){ if(height[j] < i && isHaveLeftIndex(i,j,height) && isHaveRightIndex(i,j,height)){ res++; } } } return res; } public Boolean isHaveLeftIndex(int mH,int index,int [] height){ for(int i = 0;i < index;i++){ if(height[i] >= mH) return true; } return false; } public Boolean isHaveRightIndex(int mH,int index,int [] height){ for(int i = index+1;i < height.length;i++){ if(height[i] >= mH) return true; } return false; } }
解法三
维护两个数组
max_left[i] 保存i左边大于height[i]的值
max_right [i] 保存i右边大于height[i]的值
和解法一类似
class Solution { public int trap(int[] height) { int res = 0; int len = height.length; int[] max_left = new int[len]; int[] max_right = new int[len]; for(int i = 1;i < len-1;i++){ max_left[i] = Math.max(max_left[i-1],height[i-1]); } for(int i = len -2;i > 0;i--){ max_right[i] = Math.max(max_right[i+1],height[i+1]); } for(int i = 1;i < len-1;i++){ if(max_left[i] > height[i] && max_right[i] > height[i]){ res = res + Math.min(max_left[i],max_right[i]) - height[i]; } } return res; } }
解法四
双指针
维护一个leftMax与rightMax
一个left，一个right同时往中间靠
如果height[left] < height[right] 那么leftMax一定小于rightMax
class Solution { public int trap(int[] height) { int res = 0; int len = height.length; int left = 0; int right = len-1; int leftMax = 0; int rightMax = 0; while(left < right){ leftMax = Math.max(leftMax,height[left]); rightMax = Math.max(rightMax,height[right]); if(height[left] < height[right]){ res = res + leftMax-height[left]; left++; }else{ res = res + rightMax-height[right]; right--; } } return res; } }
解法五
单调栈
维护一个高度递减的单调栈，栈中存的下标
当出现height[i]>height[stack.peek()时并且stack中至少有两个元素，那么就找到了一个可以接雨水的地方，如果栈中只有一个元素那么加上这个元素也只有两个元素不能接雨水
class Solution { public int trap(int[] height) { int res = 0; int len = height.length; Stack<Integer> stack = new Stack<>(); for(int i = 0;i < len;i++){ while(!stack.isEmpty() && height[i] > height[stack.peek()]){ int top = stack.pop(); if(stack.isEmpty()) break; int left = stack.peek(); res = res + (i - left - 1) * (Math.min(height[left],height[i])-height[top]); } stack.add(i); } return res; } }
柱状图中最大的矩形
解法一
暴力
遍历数组，计算以当前height[i]为高的矩形的面积
向左找到最左边大等于height[i]的下标
向右找到最左边大等于height[i]的下标
然后计算面积
class Solution { public int largestRectangleArea(int[] heights) { int len = heights.length; int left = 0; int right = 0; int res = 0; for(int i = 0;i < len;i++){ left = right = i; while(left > 0 && heights[left-1] >= heights[i]){ left--; } while(right < len-1 && heights[right+1] >= heights[i]){ right++; } res = Math.max(res,(right-left+1)*heights[i]); } return res; } }
解法二
单调栈
栈中保存递增的height[i]的下标
如果当前height[i]小于height[stack.peek()]那么以height[stack.pop()]为高的面积就能够确定
class Solution { public int largestRectangleArea(int[] heights) { int len = heights.length; int res = 0; Stack<Integer> stack = new Stack<>(); for(int i = 0;i < len;i++){ while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){ int top = stack.pop(); // height[top]高度的长方形面积可以确定 if(stack.isEmpty()){ // 说明top之前的都比heigh[top]高 res = Math.max(res,i*heights[top]); }else{ int left = stack.peek(); res = Math.max(res,(i-left-1)*heights[top]); } } stack.add(i); } //可能还剩下全是递增的 while(!stack.isEmpty() && -1 < heights[stack.peek()]){ int top = stack.pop(); if(stack.isEmpty()){ res = Math.max(res,len*heights[top]); }else{ int left = stack.peek(); res = Math.max(res,(len-left-1)*heights[top]); } } return res; } }
每日温度
解法一
暴力遍历
class Solution { public int[] dailyTemperatures(int[] temperatures) { int len = temperatures.length; if(len == 0) return null; int[] ans = new int[len]; for(int i = 0;i < len ;i++){ for(int j = i+1;j < len;j++){ if(temperatures[j] > temperatures[i]){ ans[i] = j-i; break; } } } return ans; } }
解法二
单调栈
维护一个温度单调递减的栈
如果temperatures[i] > temperatures[stack.peek()]则找到下标为stack.peek()的下一个更高温度
class Solution { public int[] dailyTemperatures(int[] temperatures) { int len = temperatures.length; if(len == 0) return null; Stack<Integer> stack = new Stack<>(); int[] ans = new int[len]; for(int i = 0;i < len ;i++){ while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()] ){ int top = stack.pop(); ans[top] = i-top; } stack.add(i); } return ans; } }
