42. 接雨水

题目是这样的：给 n 个非负整数，每个数是一根宽度为 1 的柱子的高度，柱子按这个顺序排成一排，下雨之后能接住多少水（题目出处：力扣 42 题面）。官方例子：[0,1,0,2,1,0,1,3,2,1,2,1] 能接 6 个单位的水；[4,2,0,3,2,5] 能接 9 个单位的水。n 最多到 20000，柱子高度最多到 100000。

一个位置能接多少水，只看两边最高的柱子

先不想整排柱子，只看其中一根。它的头顶能不能存住水，取决于两边有没有更高的柱子挡着。左边最高的柱子有多高，右边最高的柱子有多高，水面只能涨到两边里矮的那一个，再减掉这根柱子自己的高度，就是这个位置接的水。矮的那边漏了，水就从矮的那边流走，所以水位是两边最高里矮的那个，不是高的那个。

拿官方第一个例子验一下。位置 2 高 0，左边最高 1，右边最高 3，接 1；位置 5 高 0，左右最高是 2 和 3，接 2；位置 4 和位置 6 各接 1，位置 9 也接 1。其他位置一滴都接不住：位置 0 左边没有柱子，位置 1 左边最高就是它自己，位置 3 左边最高就是它自己，位置 7 是整排最高的柱子，位置 8、10、11 右边最高就是自己或比自己矮。1 + 1 + 2 + 1 + 1，正好是 6。

第二个例子也一样：[4,2,0,3,2,5]，位置 1 接 2，位置 2 接 4，位置 3 接 1，位置 4 接 2，加起来是 9。两头的柱子永远接不住水，因为一侧没有东西挡着。

最直接的做法：每个位置左右各扫一遍

对每个位置，向左扫一遍找最高的，向右扫一遍找最高的，取矮的那个减去自己的高度，负数算 0。

def trap_naive(height):
    n = len(height)
    total = 0
    for i in range(n):
        left_max = max(height[: i + 1])  # 左边最高的，含自己
        right_max = max(height[i:])      # 右边最高的，含自己
        total += max(0, min(left_max, right_max) - height[i])
    return total

这份代码是对的，官方两个例子全过，3000 组随机数据和后面的正式解法对拍也没有一组失配（随机种子 20261112，每组长度 0 到 15，高度 0 到 5）。但它慢，慢在每个位置都要重扫两边。n 个位置，每个位置扫 O(n)，合起来是 O(n^2)。本地实测，2000 根柱子、高度 0 到 9（随机种子 7，全新的 Random(7) 用 randint 逐个生成），这份做法要 0.0730 秒；柱子涨到 20000 根（随机种子 7，同样做法），要 6.6537 秒。柱子变成 10 倍，用时涨了约 91 倍。

先把两边的最高算出来：两遍预处理

位置 i 左边的最高，和位置 i+1 左边的最高，几乎是同一个东西，只差一根柱子。左边的最高从左往右扫一遍就能全算出来，右边的最高从右往左扫一遍也一样。先把这两排数算好存在数组里，再逐个位置求和，就不用每个位置重扫了。

def trap_prefix(height):
    n = len(height)
    if n == 0:
        return 0
    left_max = [0] * n
    right_max = [0] * n
    cur = 0
    for i in range(n):  # 从左往右，左边最高的
        cur = max(cur, height[i])
        left_max[i] = cur
    cur = 0
    for i in range(n - 1, -1, -1):  # 从右往左，右边最高的
        cur = max(cur, height[i])
        right_max[i] = cur
    total = 0
    for i in range(n):
        total += max(0, min(left_max[i], right_max[i]) - height[i])
    return total

拿自己造的一组数走一遍，[3,0,0,2,0,4]：从左往右的最高是 [3,3,3,3,3,4]，从右往左的最高是 [4,4,4,4,4,4]，四个低位置接的水是 3、3、1、3，加起来是 10。本地实测也是 10，三种解法结果一致。

这份代码时间是 O(n)，三遍线性扫描。代价是多用了两个数组，空间 O(n)。本地实测，2000 根柱子（随机种子 7，同样做法）只要 0.0012 秒，20000 根柱子（随机种子 7，同样做法）只要 0.0118 秒。柱子变成 10 倍，用时只涨了约 10 倍。

双指针：矮的那一侧先算

两个数组还能不能省掉？能。左指针从最左往右走，右指针从最右往左走，各记一个走过的最高。双指针多了一个判断：矮的那一侧先算。

为什么矮侧可以先算？假如左边的指针指着的柱子比右边的矮，那么右边的最高至少有右边这根柱子那么高，也就是至少不低于左边的柱子。左边的最高和右边的最高里，矮的一定是左边那个，左边的水位在这一刻已经定了，不用等右指针走完。反过来也一样：右边矮，就先算右边。所以每次只动矮的那一侧，另一侧不动。

拿 [4,2,0,3,2,5] 走一遍：左指针先看最左边的 4，4 刷新左边最高；接着 2 接 2，0 接 4，3 接 1，2 接 2；左指针走到最右边的 5，和右指针碰头，5 是左边最高的，不接水。2 + 4 + 1 + 2 = 9，和官方答案一致。

def trap_two_pointer(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    total = 0
    while left <= right:
        if height[left] <= height[right]:  # 左边矮，先算左边
            if height[left] >= left_max:
                left_max = height[left]  # 刷新最高，不接水
            else:
                total += left_max - height[left]
            left += 1
        else:  # 右边矮，先算右边
            if height[right] >= right_max:
                right_max = height[right]
            else:
                total += right_max - height[right]
            right -= 1
    return total

两边高度相等的时候走哪边都行：另一侧至少有一样高的柱子挡着，先算的这一侧水位一样能定。代码里写的是 <=，相等时先算左边，换成 < 先算右边结果也一样，3000 组随机对拍里两种写法没有一组失配。

这份代码时间 O(n)，每个位置只走一遍，额外空间 O(1)，只用了几个变量。本地实测，2000 根柱子（随机种子 7，同样做法）只要 0.0002 秒，20000 根柱子（随机种子 7，同样做法）只要 0.0024 秒。20000 根柱子的时候，朴素做法的 6.6537 秒是它的约 2770 倍。

三个容易踩的坑

第一个坑是水位取高取矮。接多少水看的是两边最高里矮的那一个，取成高的那个就多算了。位置 5 那根 0 高的柱子，左边最高 2，右边最高 3，水位是 2 不是 3，接 2 不是 3。

第二个坑是两边最高含不含自己。我的两份代码里，左边最高和右边最高都含自己这根柱子，所以 min(左最高, 右最高) - height[i] 不会是负数，max(0, …) 只是兜底。如果写成不含自己的左右最高，差值就可能变负，max(0, …) 就不能省。两种写法都对，别混着用。

第三个坑是双指针的移动顺序。必须动矮的那一侧，动高的那一侧就错了：高的那一侧的水位还没定，另一侧的最高可能比它还矮，提前算就多算了。还有刷新最高的顺序：先判断当前柱子是不是超过了已知的最高，超过了就刷新、不接水；没超过才把差值加上。反过来写，先加差值再刷新，高的柱子也会多出一笔。

另外两个边界不用特殊处理：单调递增 [1,2,3,4,5] 和单调递减 [5,4,3,2,1] 都接不住水，因为一侧永远没有更高的柱子挡着，本地实测都是 0；空数组和一根柱子也接不住，本地实测都是 0。题目给的约束本来就是 n 至少是 1，空数组只是代码里顺手兜了个底。

复杂度再算一遍

朴素版：时间 O(n^2)，每个位置重扫两边；额外空间 O(1)。前缀版：时间 O(n)，三遍线性扫描；空间 O(n)，两个数组。双指针版：时间 O(n)，每个位置只走一遍；额外空间 O(1)。单调栈也能做这道题，按一层一层横着算。

从朴素到前缀，省的是重复扫描；从前缀到双指针，省的是两个数组。省数组的代价是多了一句推理：矮侧的水位当场就能定。这句话想明白了，代码里那行判断就是顺着它写出来的。