给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例
解题思路：暴力(含优化) / 单调栈
首先我们分析一下，针对【第 i 列】什么时候可以接雨水呢？（0 ≤ i ＜ n）
——当出现凹槽的时候，也就是这一列的左边出现高墙，右边也出现高墙的时候！
——更进一步的，这一列能接雨水的最大值取决于它的左边最高的高墙（也就是：height[0], height[1], ……, height[ i-1 ]中的最大值），以及右边最高的高墙（也就是：height[ i+1 ], height[ i+2 ], ……, height[ n-1 ]中的最大值），取这两者的最小值（短板效应）！
1、解法一：暴力 )
● 遍历第 i 列，需要一层for循环——
● 分别找到左边的最大值，右边的最大值，需要两层并列的for循环——，嵌套后时间复杂度为
● 计算当前列接雨水的最大量
class Solution {
public int trap(int[] height) {
int result = 0;
for(int i=0; i<height.length; i++){
if(i == 0 || i == height.length-1) continue; // 第0列和最后一列不接雨水
// 找到左边最高高墙
int leftMaxIndex = -1;
int leftMaxHeight = height[i];
for(int j=i-1; j>=0; j--){
if(height[j] > leftMaxHeight){
leftMaxHeight = height[j];
leftMaxIndex = j;
}
}
// 找到右边最高高墙
int rightMaxIndex = -1;
int rightMaxHeight = height[i];
for(int j=i+1; j<height.length; j++){
if(height[j] > rightMaxHeight){
rightMaxHeight = height[j];
rightMaxIndex = j;
}
}
if(leftMaxIndex == -1 || rightMaxHeight == -1) continue; // 说明无法接雨水
result += (Math.min(leftMaxHeight, rightMaxHeight) - height[i]);
}
return result;
}
}
2、解法二：暴力优化 )
基本思想还是解法一。我们发现，在找左边最大值和右边最大值的过程中，出现了很多重复计算。
因此，可以直接在最开始维护两个数组：
● leftMaxArr[i]：第 i 列左边的最大值（不包括第 i 列）——1层for循环，
● rightMaxArr[i]：第 i 列右边的最大值（不包括第 i 列）——1层for循环，
遍历第 i 列，计算接雨水时，直接从上面两个数组中取。——1层for循环，
三层for循环并列，所以总的时间复杂度为
class Solution {
public int trap(int[] height) {
int result = 0;
// 预处理部分
int[] leftMaxArr = new int[height.length];
int[] rightMaxArr = new int[height.length];
int curMax = height[0];
for(int i=1; i<height.length; i++){
leftMaxArr[i] = curMax;
if(height[i] > curMax) curMax = height[i];
}
curMax = height[height.length-1];
for(int i=height.length-2; i>=0; i--){
rightMaxArr[i] = curMax;
if(height[i] > curMax) curMax = height[i];
}
for(int i=0; i<height.length; i++){
if(i == 0 || i == height.length-1) continue; // 第0列和最后一列不接雨水
if(leftMaxArr[i] <= height[i] || rightMaxArr[i] <= height[i]) continue; // 说明无法接雨水
result += (Math.min(leftMaxArr[i], rightMaxArr[i]) - height[i]);
}
return result;
}
}
3、解法三：单调栈
● 什么时候要想到用单调栈？
——通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素！
在接雨水这道题中，我们要寻找凹槽，即第 i 列比它高的 左侧高墙和右侧高墙，应该要能够想到借助单调栈求解。
● 凹槽的寻找
——如果我们知道了凹槽（高低高）在两处制高点的下标，那么我们就可以求制低点的接雨水量。
遍历第 i 列时，我们维护一个严格单调递减的栈（保存下标）：——1层for循环，时间复杂度
● 如果第 i 列（当前柱子）高度 ＜ 栈顶，直接压入当前柱子的下标 i
● 如果第 i 列（当前柱子）高度 ≥ 栈顶，那么就有可能形成凹槽。
弹出栈顶元素（凹槽的最低点）后，再取一次栈顶元素（如果存在，那么就是凹槽另一侧最高点），计算这个凹槽中的【接雨水量 = min(左侧制高点高度, 右侧制高点高度) - height[i]】。最后将 i 压入栈，因为它可能构成下一个凹槽。
class Solution {
private int result = 0;
public int trap(int[] height) {
// 严格单调递减栈，里面存放下标
LinkedList<Integer> stack = new LinkedList<>();
for(int i=0; i<height.length; i++){
if(stack.isEmpty() || height[stack.getLast()] > height[i]) stack.addLast(i);
else{
while(!stack.isEmpty() && height[stack.getLast()] <= height[i]){
stack.removeLast();// 弹出凹槽最低点
if(!stack.isEmpty()) calWater(height, stack.getLast(), i);// 凹槽左测最高点 凹槽右侧最高点
}
stack.addLast(i);
}
}
return result;
}
// 在height[l:r]中接雨水，目标值是height[l]、height[r]中小的那个
public void calWater(int[] height, int l, int r){
int target = (height[l] <= height[r] ? height[l] : height[r]); // 取最小的那个
for(int i=l; i<=r; i++){
if(target <= height[i]) continue;
result += target - height[i]; // 计算注水量
height[i] = target; // 注水
}
}
}
再多说两句单调栈解法和暴力的区别：
⭕ 与暴力解法不同之处在于：
● 暴力求解每一列时从全局出发，【一次性】计算出该列最大接雨水量。
暴力一次性求解
● 单调栈求解时，只能基于当前的凹槽（高低高），并不能保证当前列已经求解完了，它是一个【累积】的过程！
单调栈积累求解
举个例子，假设有：[2,1,0,1,3]，我们考察第2列（当前雨水量为0）：
● 暴力解法，直接求解到第2列左侧最大是2，右侧最大是3
那么此时求解第2列：可接的雨水量=min(2, 3) - height[2] = 2
● 单调栈的解法，探查到第一个凹槽是[1, _, 1]，此时给第2列，计算的可接雨水量=min(1, 1) - height[2] = 1
探查到第二个凹槽是[2, _, 3]，此时再给第2列，计算可接雨水量=min(2, 3) - height[2]（此时已经变成了1）=1
——因此它是分步累积的！
