代码随想录：动态规划4-5
42.接雨水
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5] 输出：9
代码
class Solution {
public int trap(int[] height) {
//雨水的关键是找凹槽，凹槽是栈顶的mid，右边柱子是当前更大的元素，左边的柱子是栈顶下面的元素
//单调递减栈：寻找右边第一个更大的元素
Stack<Integer> stack = new Stack<>();
//栈中放的是元素下标，第一个元素入栈,高度=height[0]
stack.push(0);
int sum = 0; //初始雨水
//i是当前元素下标，height[i]是当前元素高度
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(); //凹槽下标
//mid出栈后，如果栈为空，说明mid左边是空的，没有雨水,[1],mid=1，1出栈就行
//mid出栈后，如果栈非空，说明mid左边不空，有雨水，需要计算雨水量
if(!stack.isEmpty()){
int left = stack.peek(); //凹槽左边下标
//mid凹槽的雨水高度 = 左右高度最小值-凹槽高度
int h = Math.min(height[i], height[left]) - height[mid];
//mid凹槽的雨水宽度
int w = i - left - 1; //这里要写- left - 1，不能写-mid，[4,2,0,3,2,5]画个图就知道了
int area = h * w; //mid凹槽雨水量
sum += area;
}
}
stack.push(i);//当前元素下标入栈
}
}
return sum; //返回总雨水量
}
}84.柱状图中最大的矩形
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4] 输出： 4
代码
class Solution {
public int largestRectangleArea(int[] heights) {
//关键是找变小的元素，变小了，就把前面的矩形面积计算出来
//扩容，头尾加元素0
int[] newHeights = new int[heights.length + 2];
//头部加0，防止出现[8,6,4,2]递减序列算出来是0
newHeights[0] = 0;
//尾部加0，防止出现[2,4,6,8]递增序列算出来是0
newHeights[newHeights.length - 1] = 0;
//数组copy
for(int i=0; i < heights.length; i++){
newHeights[i+1] = heights[i];
}
int res = 0; //初始最大面积
//单调栈，找右边第一个更小的元素
Stack<Integer> stack = new Stack<>();
//第一个元素下标入栈
stack.push(0);
for(int i=1; i < newHeights.length; i++){
//当前元素高度 > 栈顶元素高度
//举例：[1,5,6]持续入栈
if(newHeights[i] > newHeights[stack.peek()]){
stack.push(i); //下标入栈
}
//当前元素高度 = 栈顶元素高度
//举例：[1,5,5,6]，当前元素=2,最大值会在第一个5取到，5不用出栈
else if(newHeights[i] == newHeights[stack.peek()]){
stack.push(i); //下标入栈
}
//当前元素高度 < 栈顶元素高度
else{
//[1,5,6],当前元素=2，要出栈循环计算矩形大小
while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]){
int mid = stack.pop(); //6的下标
if(!stack.isEmpty()){
int left = stack.peek(); //5的下标
int h = newHeights[mid]; //高度是6
int w = i - left - 1; //宽度是1
int area = h * w; //面积是6
res = Math.max(res, area); //更新最大矩形面积
}
}
stack.push(i);
}
}
return res;
}
}