42. Trapping Rain Water

问题

给定一个长度为 n 的非负整数，表示一个高度图，其中每个条的宽度为 1，计算它在雨后能够捕获多少水。

上述高度图由数组 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 表示。在这种情况下，6 个单位的雨水（蓝色部分）被捕获。

例子：

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

思路

这个题目和第 11 题很像，因此我们可以采取相同的思路，用一个头指针和尾指针进行一次 one-pass 迭代。每次循环，我们需要做三件事情。

• 改变头指针或尾指针的位置 — l, r：和 11 题一样，谁是短板就不要谁。

• 确定水位 — level：水位是短板和原先水位的最大值。

• 确定蓄水量 — water：蓄水量是水位减去短板（这也就是说，如果你的水位被更新成了短板，那么将不会蓄水；如果短板不如水位高，就会有蓄水）。

最后，我们用一个简单的例子来验证这种算法的正确性，例子中高度图由 [3, x, 5] 表示。我们需要讨论三种情况：

1. 当 x = 1 时：这时候，第一次迭代确定了水位为 3，蓄水量为 0，并且更新 l = 1, r = 2。第二次迭代没有改变水位，水位依然为 3（因为 1 < 3），但是蓄水量为 3 - 1 = 2，并更新 l = r = 2。循环结束，蓄水量为 2，水位为 3，结果正确。

2. 当 x = 4 时：这时候，第一次迭代确定了水位为 3，蓄水量为 0，并且更新 l = 1, r = 2。第二次迭代确定了水位为 4 （因为 4 > 3），蓄水量为 3 - 3 = 0，并更新 l = r = 2。循环结束，蓄水量为 0，水位为 4，结果正确。

3. 当 x = 8 时：这时候，第一次迭代确定了水位为 3，蓄水量为 0，并且更新 l = 1, r = 2。第二次迭代确定了水位为 5（因为 5 > 3），蓄水量为 5 - 5 = 0（此时 5 为短板），并更新 l = r = 2。循环结束，蓄水量为 0，水位为 5，结果正确。

答案

class Solution:

    def trap(self, height: List[int]) -> int:

        l, r = 0, len(height) - 1
        water = level = 0
        while l < r:
            if height[l] < height[r]: 
                lower = height[l]
                l += 1
            else:
                lower = height[r]
                r -= 1
            level = max(lower, level)
            water += level - lower
        return water