42. 接雨水 (Hard)

专题归类： 02-双指针与滑动窗口 · 05-单调栈 · 06-动态规划 LeetCode 链接： https://leetcode.cn/problems/trapping-rain-water/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

示例：

输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
输出：6
解释：数组表示柱子的高度图，下雨后能接 6 个单位的雨水

补充说明：

• 柱子数量范围：n == height.length，1 <= n <= 2 * 10^4
• 高度范围：0 <= height[i] <= 10^5

---

题目详细分析

数据范围含义：

• n 最大 2×10^4，O(n^2) 的解法（约 4×10^8 次操作）不可行。需要 O(n) 或 O(n log n) 的解法。
• 高度最大 10

核心约束：

• 每个位置能接的雨水量由该位置左右两侧最大高度中的较小值减去当前高度决定。
• 公式：water[i] = max(0, min(left_max[i], right_max[i]) - height[i])
• 这个公式是解题的核心。理解它需要想象：雨水被”困”在柱子之间，需要两侧都有比中间高的柱子才能存水。
• 柱子本身不占水量（宽度为 1 的柱子位置本身不能存水，水在柱子之间）。

边界条件：

• 高度全为 0：无法接水，结果为 0。
• 高度递增：如 [1, 2, 3, 4, 5]，每个位置右边都比左边高，无法存水，结果为 0。
• 高度递减：如 [5, 4, 3, 2, 1]，同理无法存水。
• 最少 1 根柱子：不足 3 根时无法存水（需要至少左、中、右三根）。

隐藏条件：

• “木桶效应”——每个位置的水位由左右两侧最高柱子中较矮的那根决定。
• 双指针优化的关键：不需要同时知道两侧的最大高度。当 left_max < right_max 时，左指针处的水量就由 left_max - height[left] 决定，因为右边至少有一个柱子比 left_max 高（就是当前的 right_max），水不会从右边溢出。

---

小白版直白理解

想象一排高度不同的积木立在桌面上，你在积木之间倒水。

水会积在凹进去的地方。比如两边的高积木中间夹着一块矮积木，水就积在矮积木的两侧，被两边的”墙”挡住。

每个位置能存多少水？你要看这个位置左边最高的积木和右边最高的积木——水会从较矮的那边”溢出去”，所以水位只能到较矮的那边的高度。水位减去当前积木的高度，就是这块位置能存的水量。

笨办法： 对每个位置，分别往左看、往右看，找到两边的最高积木。每个位置都要 O(n) 时间找最大，总共 O(n

聪明办法（双指针）： 你用两个指针从左右两端向中间走，同时记下当前左边遇到的最大高度和右边遇到的最大高度。如果左边的最大高度小于右边的，那么左指针位置的水量就确定了（因为右边的最大高度已经能兜住水了），左指针往右走。反之，右指针往左走。

---

解题思路

思路一：双指针法（推荐，最优）

关键洞察： 每个位置的水量取决于 min(left_max, right_max) - height[i]。双指针法不需要提前计算所有位置的左右最大值，而是在遍历过程中动态维护，并且只关心较小那一侧的水量。

核心推理：

• 维护 left_max（左指针左侧的最大值）和 right_max（右指针右侧的最大值）。
• 如果 left_max < right_max，对于左指针指向的位置：
  • 它的左边最高就是 left_max。
  • 右边至少有一个 right_max 比 left_max 大（可能不是全局最高，但已经足够兜住水了）。
  • 所以该位置的水量 = left_max - height[left]（如果为正）。
  • 左指针右移。
• 反之，处理右指针。

def trap(height):
    """
    双指针法
    维护 left_max 和 right_max，每次处理较矮一侧
    
    步骤：
    1. left 和 right 从两端向中间移动
    2. 维护左右两侧已遇到的最大高度
    3. 哪一侧的最大高度更小，就先处理哪一侧的当前位置
    """
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    res = 0
    
    while left < right:
        # 更新左右两侧的最大高度
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])
        
        if left_max < right_max:
            # 左边最高 < 右边最高，左指针处的水量由 left_max 决定
            res += left_max - height[left]
            left += 1
        else:
            # 右边最高 <= 左边最高，右指针处的水量由 right_max 决定
            res += right_max - height[right]
            right -= 1
    
    return res

思路二：动态规划法（好理解）

核心想法： 先预处理每个位置左右两侧的最大高度，再遍历一次累加水量。

需要 O(n) 额外空间，但思路最直观。

def trap_dp(height):
    """
    动态规划法
    预处理每个位置的左侧最大高度和右侧最大高度
    
    步骤：
    1. 从左到右遍历，记录 left_max[i]
    2. 从右到左遍历，记录 right_max[i]
    3. 再次遍历，累加 min(left_max[i], right_max[i]) - height[i]
    """
    n = len(height)
    if n < 3:
        return 0
    
    left_max = [0] * n
    right_max = [0] * n
    
    # 左侧最大值
    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])
    
    # 计算水量
    res = 0
    for i in range(n):
        res += min(left_max[i], right_max[i]) - height[i]
    
    return res

思路三：单调栈法（另一种优雅思路）

核心想法： 维护一个单调递减栈（栈底到栈顶从大到小递减）。当遇到比栈顶大的元素时，说明出现了”右边界”，可以弹栈计算水量。

关键洞察： 单调栈法的本质是在找”凹槽”。每次弹栈时，弹出的元素就是”凹槽底部”，新的栈顶是”左边界”，当前元素是”右边界”。

def trap_stack(height):
    """
    单调栈法
    维护递减栈，遇到比栈顶高的柱子就弹栈计算水量
    """
    stack = []
    res = 0
    
    for i in range(len(height)):
        # 当前柱子比栈顶高，形成凹槽
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()  # 凹槽底部
            if not stack:
                break  # 左侧没有柱子，无法存水
            left = stack[-1]  # 左边界
            width = i - left - 1
            h = min(height[left], height[i]) - height[bottom]
            res += width * h
        stack.append(i)
    
    return res

---

易错点

• 双指针中的水量计算： 是 left_max - height[left] 而不是 min(left_max, right_max) - height[left]。在 left_max < right_max 的条件下，left_max 就是 min(left_max, right_max)，直接减即可。
• DP 的初始化： left_max[0] = height[0]，right_max[n-1] = height[n-1]。边界位置不能存水。
• 单调栈的边界处理： 弹栈后如果 stack 为空，说明左侧没有更高的柱子，无法形成凹槽，break 跳出。
• 单调栈的水量公式： 是 min(height[left], height[i]) - height[bottom]（左右边界的较矮者减去底部高度），再乘以宽度（i - left - 1）。
• 小于 3 根柱子： 直接返回 0，无法存水。
• 水量可能为负： 实际上 min(left_max, right_max) - height[i] 可能为负，需要用 max(0, ...) 或等到计算时才处理。双指针法在 left_max >= height[left] 的情况下自然保证了非负。

---

框架提炼

接雨水类问题的核心公式：

每个位置的水量 = max(0, min(左侧最大高度, 右侧最大高度) - 当前高度)

三种解法对应三种不同的实现方式：

解法	如何获取左右最大高度	时间复杂度	空间复杂度
双指针	动态维护两个变量	O(n)	O(1)
动态规划	预处理两个数组	O(n)	O(n)
单调栈	栈维护递减序列	O(n)	O(n)

何时用哪种方法？

• 面试首选双指针：O(1) 空间，代码简洁，但要理解推理过程。
• 如果双指针不好理解：先说 DP 法（最直观），再优化到双指针。
• 如果面试官要求不同方法：单调栈是很好的补充，体现对数据结构的理解。

---

关联题目

• 11-盛最多水的容器 — 也是双指针 + 高度问题，但盛水是找两根柱子间的最大面积（宽度 × 较矮高度），接雨水是求所有位置积水量之和。前者是”找一对”，后者是”累加全部”
• 84-柱状图中最大的矩形 — 本题的”逆问题”：接雨水找凹槽（柱子比两侧矮），柱状图找凸起（柱子比两侧高）。84 题用单调栈，接雨水也可以。两者的单调栈实现是对称的