阅读量:0
42. 接雨水
暴力法
for循环遍历每一个柱子，内层for循环找到左边和右边比它高的柱子
时间复杂度 n^2
优化：添加一个预处理
定义一个数组，存放该柱子右边比他高的柱子是哪一个
再用一个数组，存放该柱子左边比他高的柱子是哪一个
单调栈
单调栈：在每日温度题目中，其要找到右边第一个比他大的温度；适配到本题，就是找到当前柱子左边&右边 第一个比它大的温度
遍历一次就能处理完：当前遍历的元素比栈口元素大的时候，说明栈口柱子右边比它大的那个柱子找到了，它左边比它大的柱子怎么找？在栈中。
class Solution { public int trap(int[] height){ int size = height.length; if (size <= 2) return 0; // in the stack, we push the index of array // using height[] to access the real height Stack<Integer> stack = new Stack<Integer>(); stack.push(0); int sum = 0; for (int index = 1; index < size; index++){ int stackTop = stack.peek(); if (height[index] < height[stackTop]){ stack.push(index); }else if (height[index] == height[stackTop]){ // 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的index stack.pop(); stack.push(index); }else{ //pop up all lower value int heightAtIdx = height[index]; while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){ int mid = stack.pop(); if (!stack.isEmpty()){ int left = stack.peek(); int h = Math.min(height[left], height[index]) - height[mid]; int w = index - left - 1; int hold = h * w; if (hold > 0) sum += hold; //加不加大于0都一样 stackTop = stack.peek(); } } stack.push(index); } } return sum; } } - 自己再做了一遍
class Solution { public int trap(int[] height) { if(height.length <= 2) { return 0; } Stack<Integer> st = new Stack<>(); //存的是下标 st.push(0); int sum = 0; for(int i=1; i<height.length; i++) { // i 下标 height[i]值 // height[st.peek()] height[st.pop()] if(height[i] < height[st.peek()]) { st.push(i); } else if(height[i] == height[st.peek()]) { st.pop(); st.push(i); //虽然值是一样的，但下标不一样 } else { //发现凹槽了 // int stackTop = st.peek(); int right = i; //凹槽右侧高度 while(!st.empty() && height[right] > height[st.peek()]) { int mid = st.pop();//凹点 if(!st.empty()) { int left = st.peek(); int w = right-left-1; int h = Math.min(height[left], height[right]) - height[mid]; int hold = h*w; sum += hold; } } st.push(i); //体积 = w * h } } return sum; } } 双指针
与单调栈不同的是，双指针求体积求的是 竖向的体积
class Solution { public int trap(int[] height) { int len = height.length; if(len <= 2) return 0; int[]maxLeft = new int[len]; int[]maxRight = new int[len]; maxLeft[0] = height[0]; for(int i=1; i<len; i++) { maxLeft[i] = Math.max(height[i], maxLeft[i-1]); } maxRight[len-1] = height[len-1]; for(int i=len-2; i>=0; i--) { // maxLeft[i] = Math.max(height[i], maxLeft[i-1]); maxRight[i] = Math.max(height[i],maxRight[i+1]); } int sum = 0; for(int i=0; i<len; i++) { int h = Math.min(maxLeft[i],maxRight[i]) - height[i]; if(h>0) sum+=h; // h*1 } return sum; } } 84.柱状图中最大的矩形
emmm 和接雨水到底哪里一样了？？？
暴力法 双指针
遍历每一根柱子，向左向右找比它小的边界，算出面积并求最大
优化：两个数组，一个存放i左边比他矮的，一个存放i右边
单调栈
写法不一样了，栈中元素 从栈顶到栈底要 从大到小。
遍历一次就能处理完：当前遍历的元素比栈口元素小的时候，说明栈口柱子右边比它小的那个柱子找到了，它左边比它小的柱子怎么找？在栈中。
- 首尾补0
尾补0：[2，4，6，8]
首补0：[8，6，4，2]
class Solution { public int largestRectangleArea(int[] heights) { int[]newHeight = new int[heights.length+2]; for(int i=1; i<=heights.length; i++) { newHeight[i] = heights[i-1]; } heights = newHeight; //重定向 Stack<Integer> st = new Stack<Integer>(); st.push(0); int res=0; for(int i=1; i<heights.length; i++) { if(heights[i]>heights[st.peek()]) { st.push(i); } else if(heights[i] == heights[st.peek()]) { st.pop(); st.push(i); } else { //栈可能为空吗？ while(heights[i] < heights[st.peek()]) { int mid = st.peek(); st.pop(); int left = st.peek(); int right = i; int w = right - left - 1; int h = heights[mid]; res = Math.max(res, w * h); } st.push(i); } } return res; } } 