代码随想录——接雨水（双指针&动态规划&单调栈）

题目

给定 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

思路

接雨水是面试常见题目，一般有三种思路：

1. 双指针法
2. 动态规划
3. 单调栈

一、双指针法：

首先要明确是按照行来计算，还是按照列来计算

按照行计算：

按照列计算：

在实现的时候一定不要一会按照行，一会按照列计算

这里考虑按照列来计算，如果按照列的话，宽度一定是1，再把每一列的雨水的高度求出来就行了

其中每一列雨水的高度，取决于，该列左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度

比如求第四列的雨水的高度：

列4 左侧最高的柱子是列3，高度为2（用lHeight表示）
列4 右侧最高的柱子是列7，高度为3（用rHeight表示）
列4 柱子的高度为1（用height表示）
那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height
列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了

然后就是同样的思路，只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了（注意第一个柱子和最后一个柱子不接雨水）：

for(int i = 0 ; i < height.length; i++){
	// 第一个柱子和最后一个柱子不接雨水
	if(i == 0 || i == height.length - 1){
		continue;
	}
}
1
2
3
4
5
6

java代码如下：

class Solution{
	public int trap(int[] height){
		int sum = 0;
		for(int i = 0; i < height.length; i++){
			if(i == 0 || i == height.length - 1){
				continue;
			}
			//记录左边和右边柱子的最高高度，初始化为当前柱子高度
			int rHeight = height[i];
			int lHeight = height[i];
			for(int r = i + 1; r < height.length; r++){//右柱子
				if(height[r] > rHeight){
					rHeight = height[r];
				}
			}
			for(int l = i - 1; l >= 0 ; l--){//左柱子
				if(height[l] > lHeight){
					lHeight = height[l];
				}
			}
			int h = Math.min(lHeight,rHeight) - height[i];
			if(h > 0) sum += h;
		}
		return sum;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

二、动态规划：

在双指针法中，只要记录左边柱子的最高高度 和 右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算

当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度

为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算，这就用到了动态规划

当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值（品，你细品）
即
从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1])
从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1])

java代码如下：

class Solution {
	public int trap(int[] height){
		int length = height.length;
		if(length <= 2){
			return 0;
		}
		int[] maxLeft = new int[length];
		int[] maxRight = new int[length];

		//记录每个柱子左边柱子最大高度
		maxLeft[0] = height[0];
		for(int i = 1; i < length; i++){
			maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
		}
		//记录每个柱子右边柱子最大高度
		maxRight[length - 1] = height[length -1];
		for(int i = length- 2; i >= 0; i--){
			maxRight[i] = Math.max(height[i],maxRight[i+1]);
		}
		int sum = 0;
		for(int i = 0; i < length; i++){
			int count = Math.min(maxLeft[i],maxRight[i]) - height[i];
			if(count > 0) sum += count;
		}
		return sum;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

三、单调栈：

1. 使用单调栈，是按照行来计算雨水的：
   

2. 单调栈的顺序
   维护一个递减栈，一旦发现添加的柱子大于栈顶元素，进行操作，此时就代表出现了一个凹槽了，此时的栈顶元素表示凹槽，要添加的柱子表示凹槽右边的柱子，栈顶第二个元素表示凹槽的左边柱子

3. 遇到相同高度的柱子
   同样也是出栈顶元素（旧下标），然后把相同高度的柱子（新下标）入栈，因为要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度

4. 栈中存的元素
   栈中依旧存int类型的下标即可，如果要知道对应的高度，直接通过height[stack.peek()]获取即可

单调栈的处理逻辑：
先将下标0的柱子加入到栈中，stack.push(0)
然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)
维护一个递减栈，如果当前遍历的元素（柱子）高度小于栈顶元素的高度，直接入栈；如果等于的话，那么要更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度；如果当前遍历的元素大于栈顶元素的高度，就出现凹槽了

先取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]
此时的栈顶元素stack.peek()，就是凹槽的左边位置，下标为stack.peek()，对应的高度为height[stack.top()]
当前遍历的元素i，即，新插入的柱子，就是凹槽右边的位置，下标为i，对应的高度为height[i]
相当于就是栈顶和栈顶的下一个元素以及要入栈的三个元素来接水！
雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[stack.peek()], height[i]) - height[mid]
雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - stack.top() - 1
当前凹槽雨水的体积就是：h * w

java代码如下：

class Solution{
	public int trap(int[] height){
		int len = height.length;
		if(len < 2) return 0;
		
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(0);
		
		int sum = 0;
		for(int i = 1; i < len; i++){
			int top = stack.peek();
			if(height[i] < height[top]){//如果当前元素小于栈顶元素，直接入栈
				stack.push(i);//记住，入栈的是下标，不是下标元素
			} else if(height[i] == height[top]){
				// 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的i, push当前的i,保证右边的柱子接雨水
				stack.pop();
				stack.push(i);
			} else {//如果当前元素大于栈顶元素，则出栈顶元素，将当前元素入栈
				while(!stack.isEmpty() && height[i] > height[top]){
					int mid = stack.pop();
					if(!stack.isEmpty()){
						int left = stack.peek();
						int h = Math.min(height[left],height[i]) - height[mid];
						int w = i - left - 1;
						int store = h * w;
						if(store > 0) sum += store;  
						top = stack.peek();//更新栈顶元素
					}
				}
				stack.push(i);//这里只是拿出来用来计算一下，最终还是要入栈的
			}
		}
		return sum;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35