代码随想录算法训练营第四十九天 | 42-接雨水、84-柱状图中最大的矩形
LeetCode42 接雨水
题目链接：https://leetcode.cn/problems/trapping-rain-water/description/
文章讲解：https://programmercarl.com/0042.接雨水.html
视频讲解：https://www.bilibili.com/video/BV1uD4y1u75P/?vd_source=b989f2b109eb3b17e8178154a7de7a51
单调栈思路，按行计算雨水，横向求解
找凹槽就是求左右第一个更大的元素，单调栈从栈头到栈底是递增。一旦发现添加的柱子高度大于栈头元素，此时就发现了凹槽，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，添加的柱子就是凹槽右边的柱子
遇到相同高度的元素，将栈里元素（旧下标）弹出，再将新元素（新下标）加入栈中，因为后续求宽度时，遇到相同高度的柱子，要使用最右边的柱子来计算宽度
另外注意不要操作空栈导致空指针异常
class Solution {public int trap(int[] height) {int totalRain = 0;Deque<Integer> stack = new LinkedList<>();stack.push(0);for(int i = 1; i < height.length; i++){if(height[i] < height[stack.peek()]){stack.push(i);}else if(height[i] == height[stack.peek()]){stack.pop();stack.push(i);}else{while(!stack.isEmpty() && height[i] > height[stack.peek()]){int mid = stack.pop();if(!stack.isEmpty()){int h = Math.min(height[stack.peek()], height[i]) - height[mid];int width = i - stack.peek() - 1;totalRain += h*width;}}stack.push(i);}}return totalRain;}
}
精简版代码：
class Solution {public int trap(int[] height) {int totalRain = 0;Deque<Integer> stack = new LinkedList<>();for(int i = 0; i < height.length; i++){while(!stack.isEmpty() && height[i] > height[stack.peek()]){int mid = stack.pop();if(!stack.isEmpty()){int h = Math.min(height[stack.peek()], height[i]) - height[mid];int width = i - stack.peek() - 1;totalRain += width*h;}}stack.push(i);}return totalRain;}
}
LeetCode84 柱状图中最大的矩形
题目链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
文章讲解：https://programmercarl.com/0084.柱状图中最大的矩形.html
视频讲解：https://www.bilibili.com/video/BV1Ns4y1o7uB/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本题与LeetCode42 接雨水时相呼应的两道题，接雨水是找左右两边第一个大于该柱子高度的柱子，而本题是找左右第一个小于该柱子的柱子
找左右第一个更小的元素，单调栈从栈顶到栈底递减。栈顶和栈顶的下一个元素以及要入栈的三个元素组成了要求的最大面积的高度和宽度
heights数组末尾要加零，是因为如果数组本身升序，入栈后一定都是单调递减，一直没有计算结果，结尾加个0就会让栈内所有元素进入计算结果的情况
heights数组开头也要加0，是因为如果数组本身降序，例如[8，6，4，2]，在8入栈后，6开始与8比较，此时得到mid(8)，right(6)，但是得不到left。因为此时把mid(8)弹出了，栈内没有元素，为了避免空栈取值会跳过计算结果的逻辑，之后又将6入栈，周而复始
class Solution {public int largestRectangleArea(int[] heights) {int[] newHeights = new int[heights.length+2];newHeights[0] = 0;newHeights[heights.length+1] = 0;for(int i = 0; i < heights.length; i++){newHeights[i+1] = heights[i];}Deque<Integer> stack = new LinkedList<>();int maxArea = 0;stack.push(0);for(int i = 1; i < newHeights.length; i++){if(newHeights[i] > newHeights[stack.peek()]){stack.push(i);}else if(newHeights[i] == newHeights[stack.peek()]){stack.pop();stack.push(i);}else{while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]){int mid = stack.pop();if(!stack.isEmpty()){int h = newHeights[mid];int width = i - stack.peek() - 1;maxArea = Math.max(maxArea, h*width);}}stack.push(i);}}return maxArea;}
}