42 接雨水

题目描述#

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

知识边界#

这道题的核心是前缀最大值与后缀最大值。

对于任意位置 i，它最终能接的雨水高度，取决于：

左边最高的柱子
右边最高的柱子

只有左右两侧都足够高，当前位置才能存水。并且水位由两侧较矮的那一边决定，因此当前位置能接的雨水为：

min(左侧最高, 右侧最高) - 当前柱子高度

1. 前缀最大值数组#

用 prefixF[i] 表示从左到右，到下标 i 为止的最大高度。

例如：

prefixF[0] = height[0]
for i := 1; i < len(height); i++ {
	prefixF[i] = max(prefixF[i-1], height[i])
}

这里的含义是：

如果前面最高柱子更高，就继承前面的最大值
如果当前柱子更高，就更新为当前高度

2. 后缀最大值数组#

用 prefixB[i] 表示从右到左，从下标 i 到末尾的最大高度。

prefixB[len(height)-1] = height[len(height)-1]
for i := len(height) - 2; i >= 0; i-- {
	prefixB[i] = max(prefixB[i+1], height[i])
}

它表示当前位置右边这一整段的最高柱子高度。

3. Go 中切片的实现方式#

本题使用两个整型切片保存状态：

prefixF := make([]int, len(height))
prefixB := make([]int, len(height))

make([]int, len(height)) 会创建长度为 len(height) 的整型切片，初始值都是 0。

4. Go 中的遍历写法#

统计答案时使用：

for i, x := range height {
	ans += min(prefixB[i], prefixF[i]) - x
}

这里：

i 是下标
x 是 height[i]

5. 常见错误点#

数组初始化位置写错#

前缀最大值数组的起点必须是：

prefixF[0] = height[0]

后缀最大值数组的起点必须是：

prefixB[len(height)-1] = height[len(height)-1]

否则后续递推就会出错。

把左右相邻当成左右最高#

这里不是看相邻柱子，而是看当前位置左边整体最高值和右边整体最高值。

公式理解错误#

当前位置接水量不是：

max(左侧最高, 右侧最高) - 当前高度

而是：

min(左侧最高, 右侧最高) - 当前高度

因为水会从较低的一侧流走。

思路#

先预处理出每个位置左边最高的柱子高度和右边最高的柱子高度，再逐个位置计算该位置能接多少雨水，最后求和。

思路一#

定义两个数组：

prefixF[i]：下标 i 左侧到当前位置的最高柱子
prefixB[i]：下标 i 右侧到当前位置的最高柱子

然后对每个位置 i：

左边最高是 prefixF[i]
右边最高是 prefixB[i]
当前位置最大水位是 min(prefixF[i], prefixB[i])
去掉当前位置柱子本身的高度 height[i]
得到当前位置接水量

累加所有位置即可。

为什么这样做是正确的：

一个位置能存多少水，只由左右两边最高挡板中较矮的那个决定。前缀最大值数组和后缀最大值数组正好把这两个信息预处理出来，因此每个位置都能在线性时间内直接算出答案。

时间复杂度：

预处理前缀最大值：O(n)
预处理后缀最大值：O(n)
统计答案：O(n)

总时间复杂度为 O(n)。

空间复杂度：

额外使用了两个长度为 n 的数组，所以空间复杂度为 O(n)。

代码#

func trap(height []int) int {
	prefixF := make([]int, len(height))
	prefixB := make([]int, len(height))
	prefixF[0] = height[0]
	for i := 1; i < len(height); i++ {
		prefixF[i] = max(prefixF[i-1], height[i])
	}
	prefixB[len(height)-1] = height[len(height)-1]
	for i := len(height) - 2; i >= 0; i-- {
		prefixB[i] = max(prefixB[i+1], height[i])
	}
	ans := 0
	for i, x := range height {
		ans += min(prefixB[i], prefixF[i]) - x
	}
	return ans
}