接雨水
题目描述
给定 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
提示：
n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
解决方法
刚刚看到这题的时候我第一想法是暴力法，遍历每个数，找到两边比这个数大的数来计算存储的水量，但是时间复杂度太高，不满足题目的限制。所以，我借鉴了一些题解，发现了这种单调栈的方法。
解法一：单调栈
思路
看了上面的示例刚开始刷题的同学可能有些懵逼，那我们结合图片来理解一下，我们就用示例3的例子进行举例，他的雨水到底代表的是什么。
上图则为我们的题目描述，可以这样理解我们在地上放置了若干高度的黄色箱子，他们中间有空隙，然后我们想在他们里面插入若干蓝色箱子，并保证插入之后，这些箱子的左视图和右视图都不能看到蓝色箱子。
这里我们也系统的说一下单调栈。单调栈含义就是栈内的元素是单调的，我们这个题目用到的是递减栈（相同也可以），我们依次将元素压入栈，如果当前元素小于等于栈顶元素则入栈，如果大于栈顶元素则先将栈顶不断出栈，直到当前元素小于或等于栈顶元素为止，然后再将当前元素入栈。就比如下图的4，想入栈的话则需要2，3出栈之后才能入栈，因为4大于他俩。
首先我们依次入栈4，3，2，0我们的数组前四个元素是符合单调栈规则的。但是我们的第五个1，是大于0的。那我们就需要0出栈1入栈。但是我们这样做是为了什么呢？有什么意义呢？别急我们来看下图。
上图我们的，4，3，2，0已经入栈了，我们的另一个元素为1，栈顶元素为0，栈顶下的元素为2。那么我们在这一层接到的雨水数量怎么算呢？2，0，1这三个元素可以接住的水为一个单位(见下图)这是我们第一层接到水的数量。
注：能接到水的情况，肯定是中间低两边高，这样才可以。
因为我们需要维护一个单调栈，所以我们则需要将0出栈1入栈，那么此时栈内元素为4，3，2，1。下一位元素为1，我们入栈，此时栈内元素为4，3，2，1，1。下一元素为5，栈顶元素为1，栈顶的下一元素仍为1，则需要再下一个元素，为2，那我们求当前层接到的水的数量。
我们是通过2，1，1，5这四个元素求得第二层的接水数为1*3=3;1是因为min(2-1,5-1)=min(1,4)得来的，大家可以思考一下木桶效应。装水的多少，肯定是按最短的那个木板来的，所以高度为1，3的话是因为5的索引为6，2的索引为2，他们之间共有三个元素（3，4，5）也就是3个单位。所以为6-2-1=3。
将1出栈之后，我们栈顶元素就变成了2，下一元素变成了3，那么3，2，5这三个元素同样也可以接到水。
这是第三层的接水情况，能够接到4个单位的水，下面我们继续出栈2，那么我们的4，3，5仍然可以接到水啊。
这是我们第四层接水的情况，一共能够接到5个单位的水，那么我们总的接水数加起来，那就是
1+3+4+5=13。
代码
class Solution {
public int trap(int[] height) {
Stack<Integer> stack = new Stack<>();
//数组大小小于3，不满足条件，直接返回就好。
if(height.length < 3){
return 0;
}
int ans = 0;
for(int cur = 0; cur < height.length; cur++){
while(!stack.isEmpty() && height[cur] > height[stack.peek()]){
//栈顶元素
int pop = stack.pop();
//可能栈顶会出现相同元素的情况，如描述中的1，1
while(!stack.isEmpty() && height[pop] == height[stack.peek()]){
stack.pop();
}
//计算该层的水的单位
if(!stack.isEmpty()){
int tar = stack.peek();
int tmp = height[tar];
int min = Math.min(height[cur], tmp);
int res = (min - height[pop]) * (cur - tar - 1);
ans += res;
}
}
//将索引入栈作为记录。
stack.push(cur);
}
return ans;
}
}
解法二：动态规划
思路
对于下标 $i$，下雨后水能到达的最大高度等于下标 $i$两边的最大高度的最小值，下标$i$处能接的雨水量等于下标 $i$ 处的水能到达的最大高度减去 $height[i]$。
朴素的做法是对于数组 $height$ 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。假设数组 $height$ 的长度为 n，该做法需要对每个下标位置使用 $O(n)$ 的时间向两边扫描并得到最大高度，因此总时间复杂度是 $O(n^2)$ 。
上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 $O(n)$ 的时间内得到能接的雨水总量。使用动态规划的方法，可以在$O(n)$ 的时间内预处理得到每个位置两边的最大高度。
创建两个长度为 $n$ 的数组$leftMax$和 $rightMax$。对于 $0 \le i \lt n$，$leftMax[i]$表示下标 $i$ 及其左边的位置中，$height$ 的最大高度，$rightMax[i]$ 表示下标 $i$及其右边的位置中，$height$ 的最大高度。
显然，$leftMax[0]=height[0]$，$rightMax[n?1]=height[n?1]$。两个数组的其余元素的计算如下：
当 $1 \le i \le n-1$ 时，$leftMax[i]=max(leftMax[i?1],height[i])$；
当 $0 \le i \le n-2$ 时，$rightMax[i]=max(rightMax[i+1],height[i])$。
因此可以正向遍历数组 $height$ 得到数组 $leftMax$ 的每个元素值，反向遍历数组 $height$ 得到数组 $rightMax$ 的每个元素值。
在得到数组 $leftMax$ 和 $rightMax$ 的每个元素值之后，对于 $0 \le i \lt n$，下标 $i$ 处能接的雨水量等于 $min(leftMax[i],rightMax[i])?height[i]$。遍历每个下标位置即可得到能接的雨水总量。
动态规划做法可以由下图体现。
代码
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
转载自：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
总结
首先，刚拿到题时没什么思路，但是看了题解之后，了解到了单调栈这种方法用来解决这种两边夹的木桶装水问题。其次，经典的动态规划也可以用来解决这种装水问题，希望以后遇到类似的问题可以从这两种角度思考。