单调栈② | Java | LeetCode 接雨水 最大的矩形

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 heightStack<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当前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint 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;}
}

单调栈最核心的其实是栈顶元素