Trapping Rain Water
一排柱子并排排列，每根宽 1 个单位：height[i] 表示第 i 根柱子的高度。雨水会积在柱子之间的低洼处。只有当某根柱子的左侧和右侧都存在更高的柱子时，水才会留在这根柱子上方；越过最左边和最右边的柱子后，水就会流走。返回这一排柱子能容纳的水的总单位数。
函数
- heightinteger-array
- 每个条形的高度，从左到右
- 返回值integer
- 被困住的水的总量
约束条件
1 ≤ height.length ≤ 2 × 1040 ≤ height[i] ≤ 105- 每个柱子宽 1 个单位，水不会停留在第一个或最后一个柱子外侧。
示例
- 输入
- height = [0, 3, 1, 0, 2, 5, 1, 2]
- 输出
- 7
- 解释
- 在 3 和 5 之间的数字是 3：比 1 大 2，比 0 大 3，比 2 大 1。后面的 1 位于 5 和 2 之间，所以它表示 1。这样结果就是 7。
- 输入
- height = [4, 1, 3, 0, 5]
- 输出
- 8
- 解释
- 较低的墙是 4，因此凹陷处的水会蓄到 4 的高度：1 上方有 3 个单位，3 上方有 1 个单位，0 上方有 4 个单位，总共是 8。水会从 4 的位置溢出，在 5 起作用之前就已经溢出了。
- 输入
- height = [1, 2, 4, 2, 1]
- 输出
- 0
- 解释
- 柱子升到 4，然后又降下来。每根柱子的一侧都没有更高的柱子，所以水会流走，答案是 0。
进阶
假设这些柱子构成一个高度各不相同的二维网格，水可以向四个方向流走。这时，你会如何计算被困住的水量？
提示
逐个打开提示，每个都会多透露一点。
先不看整行，只看一根柱子。水面最高能高出柱子
i多少？哪些柱子决定了这个高度？柱子
i上方的水位是两个数中较小的一个：从起点到i之间最高柱子的高度，以及从i到终点之间最高柱子的高度。柱子i能储存的水量等于这个水位减去它自身的高度。从两端各扫描一遍，就能分别计算出这两个最大值。你只需要两个最大值中较小的那个。把一个指针放在每一端，并记录每个指针经过的最高柱子。哪个指针所在的柱子较低，它的水位就由它自己的当前最大值决定：加上这部分水，然后将该指针向内移动。指针相遇时停止。
题解
某个柱子上方的水量取决于它左右两侧可能相距很远的柱子。水位等于左侧最高柱子和右侧最高柱子中较矮的那个高度，而该柱子能蓄住的水量等于这个水位减去它自身的高度。不同解法的区别仅在于如何找到这两个最大值。
扫描每根柱子的两侧
结果正确，但无法在最大的测试中运行完毕
思路
对于每个柱子 i，从 0 扫描到 i，找出左侧最高的柱子；再从 i 扫描到末尾，找出右侧最高的柱子，然后加上 min(leftMax, rightMax) - height[i]。两次扫描都包含柱子 i，这样结果就不会变成负数，而且两端的柱子结果为 0。
每个柱子都会扫描整行：n = 2 × 10^4 表示要读取 4 × 10^8 次，其中大多数读取都在重复扫描前一个柱子。
算法
- 将
water设为 0。 - 对于每个索引
i，从 0 扫描到i，找出leftMax。 - 从
i扫描到最后一个索引，找出rightMax。 - 将
min(leftMax, rightMax) - height[i]加到water中。 - 返回
water。
def trap(height):
n = len(height)
water = 0
for i in range(n):
# The tallest bar at or left of i, and the tallest at or right of i.
left_max = 0
for j in range(i + 1):
left_max = max(left_max, height[j])
right_max = 0
for j in range(i, n):
right_max = max(right_max, height[j])
water += min(left_max, right_max) - height[i]
return water预先计算每一侧最高的柱子
思路
从 0 到 i 的最高柱子，是从 0 到 i-1 的最高柱子和 height[i] 中较大的那个。因此，从左向右遍历一遍，填充 leftMax，每个元素都根据前一个元素构建；再从右向左遍历一遍，填充 rightMax。第三遍应用公式。
对于 [0, 3, 1, 0, 2, 5, 1, 2]，各位置的水位 min(leftMax[i], rightMax[i]) 是 [0, 3, 3, 3, 3, 5, 2, 2]。减去柱子的高度后，结果是 [0, 0, 2, 3, 1, 0, 1, 0]，总和为 7。时间复杂度为 O(n)，代价是需要两个各包含 n 个数字的数组。
算法
- 从左向右填充
leftMax：leftMax[0] = height[0]，然后计算leftMax[i] = max(leftMax[i-1], height[i])。 - 从右向左填充
rightMax：rightMax[n-1] = height[n-1]，然后计算rightMax[i] = max(rightMax[i+1], height[i])。 - 对于每个索引，将
min(leftMax[i], rightMax[i]) - height[i]加到总和中。 - 返回总和。
def trap(height):
n = len(height)
left_max = [0] * n # tallest bar from index 0 to i
right_max = [0] * n # tallest bar from index i to n-1
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
water = 0
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return water两个指针向较低的一侧移动
思路
这个公式只需要较矮的墙，而两个指针可以证明哪一面较矮。让 left 从 0 开始，让 right 从最后一个索引开始，记录 leftMax 和 rightMax，也就是每个指针经过的最高柱子，包括指针当前所在的柱子，并始终移动指向较矮柱子的指针。这样，已经经过的每根柱子都不高于当前两根柱子中较高的那根，因为指针只会越过一根不高于另一个指针所指柱子的柱子。
假设 height[left] < height[right]。根据这个不变量，leftMax 至多等于 height[right]，也就是 left 右侧的一根柱子。因此，left 右边的墙至少有 leftMax 高，而它所在位置的水位恰好是 leftMax，无论两个指针之间有什么柱子都一样。当右边的柱子更矮或与左边一样高时，用对称的论证就能确定 right。
算法
- 将
left = 0、right = n-1以及leftMax、rightMax和water设为 0。 - 当
left < right时：如果height[left] < height[right]，则在需要时将leftMax更新为height[left]，加上leftMax - height[left]，并将left向右移动。 - 否则，在右侧执行相同操作，并将
right向左移动。 - 返回
water。指针相遇处的柱子最高，无法存水。
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0 # tallest bar passed so far from each end
water = 0
while left < right:
if height[left] < height[right]:
# A bar taller than height[left] waits on the right, so left_max sets the level here.
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
# A bar at least as tall as height[right] waits on the left, so right_max sets the level.
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
易错点和边界情况
- 先加水，再更新运行中的最大值。当
height[left]大于leftMax时，水量为负数，总量会减少。 - 移动较高柱子一侧的指针，但无法证明该侧的水位。在
[4, 1, 3, 0, 5]上，这种写法返回 4，而不是 8。 - 只看最近的邻居。在
[3, 0, 2, 0, 1, 0, 4]中，高度为 1 的柱子会蓄水到高度 3，这个水位由相隔两步和四步的柱子决定；答案是 12。 - 把数组两端当作墙。水会从两端流走，因此，只有一根柱子、两根柱子，或只升高或只降低的一排柱子，都只能蓄住 0 单位水。
常见问题3
接雨水问题的时间复杂度是多少？
双指针解法的时间复杂度为 O(n)，额外空间复杂度为 O(1)，因为每一步都会让一个指针向内移动。使用 leftMax 和 rightMax 数组的版本，时间复杂度也是 O(n)，但空间复杂度为 O(n)。从每个柱子向两侧扫描的时间复杂度为 O(n²)。
可以用栈解决接雨水问题吗？
是的。维护一个高度递减的索引栈。当更高的柱子出现时，弹出栈顶：它就是由新的栈顶和当前柱子围成的水池的底部。累加 (min(two walls) - floor) × (distance between the walls - 1)，并继续弹出。这样就能按水平层填充水，时间和空间复杂度均为 O(n)。
接雨水问题与盛最多水的容器问题有什么不同？
在“盛最多水的容器”问题中，线段不占空间，答案是两条线段之间面积最大的矩形。而在这里，每根柱子都是实心的，答案是所有柱子上方水量的总和。两种问题中都移动较低的一侧，原因相同：它的结果已经确定。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def trap(height):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
height = [0, 3, 1, 0, 2, 5, 1, 2]
预期输出
7