LeetCode 42. 接雨水：从暴力到双指针，四种思路一次讲透

Table of contents

题目

力扣上的题目描述只有一句话：

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

示例 1

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

（原题这里配了一张高度图，用蓝色标出了这 6 个单位的雨水。）

示例 2

输入：height = [4,2,0,3,2,5]
输出：9

提示

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

题目在说什么

换成大白话：给你一个非负整数数组 height，每个数代表一根宽度为 1 的柱子的高度，柱子从左到右紧挨着排开。下一场雨之后，柱子之间的凹槽会存住水。问：一共能存多少格水？

拿示例 2 的 height = [4, 2, 0, 3, 2, 5] 来说，画出来是这样（█ 是柱子，~ 是存住的水）：

5 |           █
4 | █ ~ ~ ~ ~ █
3 | █ ~ ~ █ ~ █
2 | █ █ ~ █ █ █
1 | █ █ ~ █ █ █
  +------------
    0 1 2 3 4 5

数一数 ~：下标 1 有 2 格，下标 2 有 4 格，下标 3 有 1 格，下标 4 有 2 格，一共 9 格。

示例 1 也可以照这样画出来数，结果是 6 格，你可以自己试一试。

这道题难就难在：一眼看过去，水是“一块一块”的，形状不规则，不知道从哪下手。下面先找到一个关键的切入点，后面四种解法都建立在它上面。

关键洞察：一根柱子头顶能存多少水？

别去想整块水的形状，只盯着一根柱子看：它头顶上能积多少水？

想象你站在下标 i 的柱子上。水要存得住，左边和右边都得有“墙”挡着：

• 往左看，最高的柱子是 left_max；
• 往右看，最高的柱子是 right_max。

水面能到多高，取决于两堵墙里矮的那一堵（木桶效应：水会从矮的那边溢出去）。所以：

下标 i 的积水量 = min(left_max, right_max) - height[i]

这里的 left_max 和 right_max 包含柱子 i 自己。这样当 i 本身就是最高点时，min(...) 等于 height[i]，积水量是 0，不会出现负数。

用这个公式验证一下上面的例子：

加起来是 9，和画图数出来的一样。

到这里，题目就变成了：怎么快速求出每个位置的 left_max 和 right_max？ 下面四种解法，就是对这个问题的四种回答。

解法一：暴力（先保证对，再想快）

最直接的做法：对每个位置，现场往左扫一遍找最大值，再往右扫一遍找最大值。

class Solution:
    def trap(self, height: list[int]) -> int:
        water = 0
        for i, bar in enumerate(height):
            # 两侧最高值都包含当前柱子，保证积水量不会是负数
            left_max = max(height[: i + 1])
            right_max = max(height[i:])
            water += min(left_max, right_max) - bar
        return water

• 时间复杂度：O(n²)。每个位置都要把数组扫一遍。
• 空间复杂度：O(1)（不算切片产生的临时列表）。

这个解法在 LeetCode 上会超时，但它非常有价值：它直接对应关键洞察里的公式，后面的优化都是在它的基础上减少重复计算。写其他解法时，也可以拿它当“标准答案”来对拍。

解法二：预处理数组（动态规划）

暴力解法慢在哪？每个位置都重新扫一遍，可相邻位置的 left_max 其实只差一点：

left_max[i] = max(left_max[i - 1], height[i])

也就是说，从左往右走一遍，就能把所有的 left_max 都算出来。right_max 同理，从右往左走一遍。

这种“逐个累积”的计算，Python 标准库里正好有现成的工具：itertools.accumulate(height, max) 会依次产出 height[0]、max(height[0], height[1])、max(前面的结果, height[2])……也就是每个位置的前缀最大值。把数组反转后做同样的事，再反转回来，就得到了后缀最大值。

from itertools import accumulate


class Solution:
    def trap(self, height: list[int]) -> int:
        # left_max[i]：height[0..i] 中的最高柱子
        left_max = list(accumulate(height, max))
        # right_max[i]：height[i..n-1] 中的最高柱子
        right_max = list(accumulate(reversed(height), max))[::-1]

        return sum(
            min(left, right) - bar
            for left, right, bar in zip(left_max, right_max, height)
        )

• 时间复杂度：O(n)。求前缀最大值、后缀最大值、累加积水，各遍历一次。
• 空间复杂度：O(n)。两个辅助数组。

这是最推荐先掌握的解法：思路直白，和公式一一对应，不容易写错。另外它对空数组也是安全的：accumulate 和 zip 遇到空输入都会产出空序列，sum 的结果自然是 0，不需要单独判断。面试时先写出它，再优化到双指针，是很自然的节奏。

解法三：双指针（把空间省到 O(1)）

解法二要存两个数组，能不能不存？

再看一眼公式：积水量只取决于 min(left_max, right_max)，也就是两边较矮的那一个。我们其实不需要同时精确知道两个值，只要能确定“哪一边更矮”就够了。

做法是：用 left、right 两个指针从两端往中间走，一路维护：

• left_max：left 左侧（含）的最高柱子；
• right_max：right 右侧（含）的最高柱子。

每一步比较 left_max 和 right_max：

• 如果 left_max < right_max：对于 left 这个位置，它左边的最高值就是 left_max，这是确定的；它右边的真实最高值，至少是 right_max（因为 right_max 只是右边一部分柱子里的最高值，中间还没看到的柱子只可能让它更高）。所以右边的墙一定比 left_max 高，left 位置的水位就由 left_max 决定，可以直接算出积水，然后 left 右移。
• 否则：对称地，right 位置的水位由 right_max 决定，算完之后 right 左移。

一句话：哪边的最高值更矮，哪边的积水量就已经确定了，先结算那一边。

class Solution:
    def trap(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        water = 0

        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])

            if left_max < right_max:
                # 左侧最高值更矮：left 处的水位已经确定
                water += left_max - height[left]
                left += 1
            else:
                # 右侧最高值更矮（或相等）：right 处的水位已经确定
                water += right_max - height[right]
                right -= 1

        return water

用 [4, 2, 0, 3, 2, 5] 走一遍：

left 走到 5 和 right 相遇，循环结束，答案 9。

为什么循环条件是 left < right，相遇的那个位置不用算吗？ 两个指针相遇的地方，一定是全局最高的柱子之一（较矮的一侧总是先移动，最高的柱子会一直“守”到最后），最高柱子头顶不会积水，所以不用算。

• 时间复杂度：O(n)。每个位置只访问一次。
• 空间复杂度：O(1)。

这是这道题的最优解。它的难点在于想清楚“为什么可以只看较矮的一边”，上面加粗的那句话就是全部的道理。

解法四：单调栈（换个角度：按层算水）

换一种切法：把水横着切成一条一条

前三种解法都是竖着切：一根柱子一根柱子地算，每根头顶有几格水。单调栈换成横着切：把水切成一条一条的“水条”，一条一条地算。

还是 [4, 2, 0, 3, 2, 5]，把 9 格水横着分成 4 条，分别用字母 A、B、C、D 标出来：

5 |           █
4 | █ D D D D █
3 | █ B B █ C █
2 | █ █ A █ █ █
1 | █ █ A █ █ █
  +------------
    0 1 2 3 4 5

加起来是 9，和前面的答案一样。

每一条水，都被三根柱子围住

仔细看每一条水，它都被三根柱子围住：下面是坑底，左边是左墙，右边是右墙。

以 A 为例：坑底是下标 2（高 0），左墙是下标 1（高 2），右墙是下标 3（高 3）。

只要知道这三根柱子，这条水就能算出来：

宽度 = 右墙下标 - 左墙下标 - 1
深度 = min(左墙高度, 右墙高度) - 坑底高度
格数 = 宽度 × 深度

四条水全部算一遍：

注意 B 的坑底是下标 1（高 2），而不是更低的下标 2。因为 B 下面那部分已经算进 A 了，B 只负责高度 2 到 3 之间的这一层。所以这里的“坑底”，指的是这一条水的底面落在哪根柱子上。

三根柱子怎么找？正好是单调栈

再看一遍每条水的三根柱子，会发现它们有固定的关系：

• 右墙：坑底右边第一根比它高的柱子；
• 左墙：坑底左边第一根不比它矮的柱子。

比如 A 的坑底是下标 2（高 0）：往右看，第一根比 0 高的是下标 3；往左看，第一根不比 0 矮的是下标 1。

这两个“第一根”，正是单调栈入门最后讲到的：一个元素出栈时，让它出栈的新元素是它右边第一个更大的；出栈后的新栈顶，是它左边第一个不比它小的。

所以做法就是：从左到右，一根一根地把柱子放进一个单调递减栈。每当新来的柱子比栈顶高：

1. 弹出栈顶，它就是坑底；
2. 弹出之后的新栈顶，就是左墙；
3. 新来的这根柱子，就是右墙；
4. 三根柱子都有了，算出这一条水。

为什么栈是递减的？和单调栈入门里的“等待区”一样：栈里放的是还没等到右墙的柱子。如果一根矮柱子左边站着一根更矮的，那根更矮的早就等到右墙、被弹走了。

一步一步走一遍

栈写成从左到右一排，左边是栈底，右边是栈顶，每个元素写成 下标(高度)。

第 1 步：下标 0（高 4）进来

• 栈是空的，直接放进去。
• 栈：[0(4)]

第 2 步：下标 1（高 2）进来

• 2 不比栈顶 0(4) 高，放进去。
• 栈：[0(4), 1(2)]

第 3 步：下标 2（高 0）进来

• 0 不比栈顶 1(2) 高，放进去。
• 栈：[0(4), 1(2), 2(0)]

到这里，柱子一路在变矮，谁都还没有右墙，所以一格水都算不出来。它们都在栈里等着。

第 4 步：下标 3（高 3）进来

• 3 比栈顶 2(0) 高：
  • 弹出 2(0)，它是坑底；
  • 新栈顶 1(2) 是左墙，下标 3 是右墙；
  • 算出水条 A：宽 3 - 1 - 1 = 1，深 min(2, 3) - 0 = 2，+2。
• 3 还比新栈顶 1(2) 高：
  • 弹出 1(2)，它是坑底；
  • 新栈顶 0(4) 是左墙，下标 3 是右墙；
  • 算出水条 B：宽 3 - 0 - 1 = 2，深 min(4, 3) - 2 = 1，+2。
• 3 不比栈顶 0(4) 高，停下，把下标 3 放进去。
• 栈：[0(4), 3(3)]，累计 4。

此刻已经算出的水（. 表示还没算到的水）：

5 |           █
4 | █ . . . . █
3 | █ B B █ . █
2 | █ █ A █ █ █
1 | █ █ A █ █ █
  +------------
    0 1 2 3 4 5

第 5 步：下标 4（高 2）进来

• 2 不比栈顶 3(3) 高，放进去。
• 栈：[0(4), 3(3), 4(2)]，累计还是 4。

第 6 步：下标 5（高 5）进来

• 5 比栈顶 4(2) 高：
  • 弹出 4(2)，它是坑底；
  • 新栈顶 3(3) 是左墙，下标 5 是右墙；
  • 算出水条 C：宽 5 - 3 - 1 = 1，深 min(3, 5) - 2 = 1，+1。
• 5 还比新栈顶 3(3) 高：
  • 弹出 3(3)，它是坑底；
  • 新栈顶 0(4) 是左墙，下标 5 是右墙；
  • 算出水条 D：宽 5 - 0 - 1 = 4，深 min(4, 5) - 3 = 1，+4。
• 5 还比新栈顶 0(4) 高：
  • 弹出 0(4)，它是坑底；
  • 但弹出后栈空了，没有左墙。左边没有东西挡着，水会流走，所以这里算不出水，直接停下。
• 把下标 5 放进去。
• 栈：[5(5)]，累计 9。

全部柱子都处理完，四条水都算出来了：

5 |           █
4 | █ D D D D █
3 | █ B B █ C █
2 | █ █ A █ █ █
1 | █ █ A █ █ █
  +------------
    0 1 2 3 4 5

答案是 9。

写成代码

class Solution:
    def trap(self, height: list[int]) -> int:
        stack: list[int] = []  # 存下标，对应高度从栈底到栈顶单调递减
        water = 0

        for right, bar in enumerate(height):
            # 当前柱子比栈顶高：栈顶成了坑底，结算这一层水
            while stack and bar > height[stack[-1]]:
                bottom = stack.pop()
                if not stack:
                    break  # 坑底左边没有墙，水存不住

                left = stack[-1]
                width = right - left - 1
                depth = min(height[left], bar) - height[bottom]
                water += width * depth

            stack.append(right)

        return water

把代码和上面的步骤对上：

• 时间复杂度：O(n)。每个下标最多入栈、出栈各一次。
• 空间复杂度：O(n)。最坏情况下（柱子一路递减）所有下标都在栈里。

单调栈在这道题上不比双指针更优，但它的价值在于思路可以迁移：“找左右两边第一个更大（或更小）的元素”是单调栈的标准用法，739. 每日温度 和 84. 柱状图中最大的矩形 都是同一个套路，后者也在 Hot 100 里。

关于代码写法的几点约定

四段代码遵循同一套约定，读起来可以互相对照：

• 命名表达含义：积水总量统一叫 water，单根柱子的高度叫 bar，左右两侧的最高值叫 left_max / right_max，单调栈里的坑底、左墙、右墙分别是 bottom、left、right，宽和深是 width、depth。不用 h、res、ans 这类看不出含义的名字。
• 用 enumerate 同时拿下标和值，不写 for i in range(len(height)) 再取 height[i]。
• 用空行把逻辑分段：初始化、主循环、返回结果之间各空一行，循环体里“更新状态”和“结算积水”也分开。
• 注释只写“为什么”，比如为什么最高值要包含当前柱子、为什么栈空就要停下，不复述代码本身。
• 类型标注用 Python 3.9+ 的内置写法 list[int]，不再从 typing 导入 List。
• 所有代码都通过了 ruff format 格式化检查和 ruff check 静态检查。

四种解法对比

容易踩的坑

1. 空数组：如果用下标手动初始化前缀数组（比如 left_max[0] = height[0]），空数组会越界，需要先判断。本文的四种写法都天然支持空数组：暴力和单调栈的循环不会执行，双指针的 0 < -1 不成立，accumulate 产出空序列。
2. 积水量算成负数：left_max 和 right_max 要包含当前柱子自己，这样 min(...) - height[i] 最小是 0。
3. 单调栈弹出后栈空：说明坑底左边没有墙，水会流走，要直接 break，不能继续算。
4. 单调栈里的比较用 > 还是 >=：这里用 >。遇到等高的柱子时直接入栈，它和前一根等高柱子之间算出的水高度为 0，不影响结果。

一句话总结

一个位置能存多少水，取决于它左右两边最高的柱子中较矮的那一个。 暴力、预处理数组、双指针都是在用不同的方式求这两个最高值；单调栈则换了个方向，按层把水一条条算出来。

附：完整测试代码

把四种解法改写成普通函数放在一起，先跑固定用例，再用暴力解法作为基准做 3000 组随机对拍。随机数用独立的 random.Random(seed) 实例，结果可以复现，也不会影响全局的随机状态：

"""对拍测试：以暴力解法为基准，验证另外三种解法。"""

import random
from collections.abc import Callable
from itertools import accumulate


def trap_brute_force(height: list[int]) -> int:
    water = 0
    for i, bar in enumerate(height):
        left_max = max(height[: i + 1])
        right_max = max(height[i:])
        water += min(left_max, right_max) - bar
    return water


def trap_prefix_max(height: list[int]) -> int:
    left_max = list(accumulate(height, max))
    right_max = list(accumulate(reversed(height), max))[::-1]
    return sum(
        min(left, right) - bar for left, right, bar in zip(left_max, right_max, height)
    )


def trap_two_pointers(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])

        if left_max < right_max:
            water += left_max - height[left]
            left += 1
        else:
            water += right_max - height[right]
            right -= 1

    return water


def trap_monotonic_stack(height: list[int]) -> int:
    stack: list[int] = []
    water = 0

    for right, bar in enumerate(height):
        while stack and bar > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break

            left = stack[-1]
            width = right - left - 1
            depth = min(height[left], bar) - height[bottom]
            water += width * depth

        stack.append(right)

    return water


SOLUTIONS: list[Callable[[list[int]], int]] = [
    trap_brute_force,
    trap_prefix_max,
    trap_two_pointers,
    trap_monotonic_stack,
]

FIXED_CASES: list[tuple[list[int], int]] = [
    ([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], 6),
    ([4, 2, 0, 3, 2, 5], 9),
    ([], 0),
    ([5], 0),
    ([1, 2, 3], 0),
    ([3, 2, 1], 0),
    ([3, 0, 3], 3),
    ([5, 1, 1, 1, 5], 12),
]


def check(solve: Callable[[list[int]], int], height: list[int], expected: int) -> None:
    actual = solve(height)
    assert actual == expected, (
        f"{solve.__name__}({height}) returned {actual}, expected {expected}"
    )


def check_fixed_cases() -> None:
    for height, expected in FIXED_CASES:
        for solve in SOLUTIONS:
            check(solve, height, expected)


def check_random_cases(rounds: int = 3000, seed: int = 0) -> None:
    rng = random.Random(seed)
    for _ in range(rounds):
        height = [rng.randint(0, 8) for _ in range(rng.randint(0, 25))]
        expected = trap_brute_force(height)
        for solve in SOLUTIONS[1:]:
            check(solve, height, expected)


def main() -> None:
    check_fixed_cases()
    check_random_cases()
    print("all passed")


if __name__ == "__main__":
    main()