42. 接雨水

hard

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

1
2
3
输入：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 个单位的雨水（蓝色部分表示雨水）。 

双指针

按列来计算：每一列雨水的高度，取决于该列左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。

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

 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
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func trap(height []int) (res int) {
	for i := 1; i < len(height)-1; i++ {
		// 左右两个柱子不接雨水
		lMax := height[i]
		rMax := height[i]
		// 分别找左右最高的柱子
		for j := 0; j < i; j++ {
			if height[j] > lMax {
				lMax = height[j]
			}
		}
		for j := i + 1; j < len(height); j++ {
			if height[j] > rMax {
				rMax = height[j]
			}
		}
		res += min(lMax, rMax) - height[i]
	}
	return
}

DP

为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。

我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight）。

这可以用动规来计算：

即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);

从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);

 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
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func trap(height []int) (res int) {
	// 用dp计算前后最大高度
	lDp, rDp := make([]int, len(height)), make([]int, len(height))
	lDp[0], rDp[len(height)-1] = height[0], height[len(height)-1]
	for i := 1; i < len(height); i++ {
		lDp[i] = max(lDp[i-1], height[i])
	}
	for i := len(height) - 2; i >= 0; i-- {
		rDp[i] = max(rDp[i+1], height[i])
	}

	for i := 1; i < len(height)-1; i++ {
		// 左右两个柱子不接雨水
		lMax := lDp[i]
		rMax := rDp[i]
		res += min(lMax, rMax) - height[i]
	}
	return
}

单调栈

构建一个栈顶到栈底元素从小到大排列的单调栈

分析

在入栈的过程中，一旦发现添加的柱子高度大于栈头元素了，就表明出现凹槽了，栈顶元素就是凹槽底部的柱子，栈顶第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子

遇到相同的元素，就更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。因为我们要求宽度的时候如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。

单调栈，其实是通过高 × 宽来计算雨水面积的。

高就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，

步骤

先将下标 0 的柱子加入到栈中（栈中存的是下标）
然后开始从下标 1 开始遍历所有的柱子
如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了
1. 取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为 mid，对应的高度为 height[mid]（就是图中的高度 1）。
2. 此时的栈顶元素 st.top()，就是凹槽的左边位置，下标为 st.top()，对应的高度为 height[st.top()]（就是图中的高度 2）。
3. 当前遍历的元素 i，就是凹槽右边的位置，下标为 i，对应的高度为 height[i]（就是图中的高度 3）。
4. 此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素来接水！
5. 那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[mid];
6. 雨水的宽度是凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;
7. 当前凹槽雨水的体积就是：h * w。

 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
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func trap(height []int) (res int) {
	stack := []int{0} // 栈顶到栈底从小到大 存放下标

	for i := 1; i < len(height); i++ {
		if height[i] < height[stack[len(stack)-1]] {
			stack = append(stack, i)
		} else if height[i] == height[stack[len(stack)-1]] {
			// 更新栈顶
			stack[len(stack)-1] = i
		} else {
			for len(stack) != 0 && height[i] > height[stack[len(stack)-1]] {
				midIndex := stack[len(stack)-1]
				stack = stack[:len(stack)-1] // 出栈
				if len(stack) == 0 {
					break
				}
				h := min(height[i], height[stack[len(stack)-1]]) - height[midIndex]
				w := i - stack[len(stack)-1] - 1
				res += h * w
			}
			stack = append(stack, i)
		}
	}
	return
}