好的，我们这次来详细讲解 LeetCode 第 42 题「接雨水」。

这是一道非常经典的题目，考察频率极高，解法也很多样，非常适合用来训练对数组、双指针、动态规划和栈等数据结构的理解。

1. 题目描述

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

示例：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

图示（可以想象一下）：

  3 |                     ████
  2 |         ████∙∙∙∙∙∙∙∙████∙∙∙∙████
  1 |   ████∙∙████∙∙∙∙████∙∙∙∙████∙∙∙∙████
  0 |∙∙████∙∙████∙∙∙∙████∙∙∙∙████∙∙∙∙████∙∙
     ——————————————————————————————————————
      0  1  0  2  1  0  1  3  2  1  2  1

（█ 表示柱子，∙ 表示雨水）

2. 问题理解

核心思路：
对于任意位置 i，它能接的雨水量，取决于它左边最高柱子和右边最高柱子中较矮的那个（木桶原理），再减去它自己的高度。

公式化：

water[i] = min(left_max[i], right_max[i]) - height[i]

其中：

• left_max[i] = 位置 i 左边（包括 i）的最高柱子高度
• right_max[i] = 位置 i 右边（包括 i）的最高柱子高度

如果 min(left_max, right_max) <= height[i]，说明这里接不住雨水（本身是较高的柱子）。

3. 解法一：暴力法（直接模拟）

思路：
对每个下标 i，分别向左、向右扫描，找出左边最高和右边最高，然后计算当前位置可接雨水。

步骤：

1. 遍历每个位置 i（从 1 到 n-2，因为两端不可能接雨水）。
2. 向左扫描找到最大高度 left_max。
3. 向右扫描找到最大高度 right_max。
4. 累加 min(left_max, right_max) - height[i]（如果大于 0）。

代码示意：

def trap(height):
    n = len(height)
    total_water = 0
    for i in range(1, n - 1):  # 首尾不会积水
        left_max = max(height[:i+1])   # 包括i本身
        right_max = max(height[i:])
        total_water += min(left_max, right_max) - height[i]
    return total_water

复杂度：

• 时间 O(n²)（每个位置左右扫描是 O(n)）
• 空间 O(1)

缺点：重复计算左右最大值。

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

思路：
提前用两个数组分别存储每个位置的 left_max 和 right_max，避免重复扫描。

步骤：

1. 创建 left_max 数组：
   • left_max[0] = height[0]
   • 从左到右：left_max[i] = max(left_max[i-1], height[i])
2. 创建 right_max 数组：
   • right_max[n-1] = height[n-1]
   • 从右到左：right_max[i] = max(right_max[i+1], height[i])
3. 遍历每个位置，累加雨水。

代码：

def trap(height):
    n = len(height)
    if n == 0:
        return 0
    
    left_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 = [0] * n
    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])
    
    total_water = 0
    for i in range(n):
        total_water += min(left_max[i], right_max[i]) - height[i]
    
    return total_water

复杂度：

• 时间 O(n)
• 空间 O(n)（用了两个辅助数组）

5. 解法三：双指针（空间优化）

思路：
我们其实不需要同时知道完整的左右最大数组。用两个指针 left 和 right 从两端向中间移动，并维护 left_max 和 right_max 变量。

关键点：

• 如果 left_max < right_max，那么左侧指针处的水量由 left_max 决定（因为右边有更高的保证）。
• 同理，如果 right_max <= left_max，右侧指针处的水量由 right_max 决定。

步骤：

1. left = 0, right = n-1
2. left_max = height[0], right_max = height[n-1]
3. total_water = 0
4. 当 left <= right：
   • 如果 height[left] < height[right]：
     • 如果 height[left] >= left_max，更新 left_max
     • 否则累加 left_max - height[left] 到总水量
     • left += 1
   • 否则：
     • 如果 height[right] >= right_max，更新 right_max
     • 否则累加 right_max - height[right] 到总水量
     • right -= 1

代码：

def trap(height):
    n = len(height)
    if n == 0:
        return 0
    
    left, right = 0, n - 1
    left_max, right_max = height[left], height[right]
    total_water = 0
    
    while left <= right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                total_water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                total_water += right_max - height[right]
            right -= 1
    
    return total_water

复杂度：

• 时间 O(n)
• 空间 O(1)（只用了几个变量）

6. 解法四：单调栈

思路：
用栈来跟踪可能积水的凹槽。栈内存放的是下标，对应的高度递减（单调递减栈）。当遇到一个比栈顶高的柱子时，说明可能形成凹槽。

步骤：

1. 初始化空栈。
2. 遍历每个柱子：
   • 当栈非空且 height[i] > height[stack[-1]]：
     • 弹出栈顶 top（当前凹槽底部）。
     • 如果栈空了，跳出内循环（没有左边界）。
     • 计算宽度：i - stack[-1] - 1
     • 计算高度：min(height[i], height[stack[-1]]) - height[top]
     • 累加水量：宽度 × 高度
   • 将 i 入栈。

代码：

def trap(height):
    stack = []
    total_water = 0
    n = len(height)
    
    for i in range(n):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[top]
            total_water += width * bounded_height
        stack.append(i)
    
    return total_water

复杂度：

• 时间 O(n)（每个下标入栈出栈一次）
• 空间 O(n)（栈空间）

7. 总结对比

实际应用：

• 面试中最常见的是双指针解法（最优，代码简洁）。
• 单调栈解法有助于理解栈在处理区间问题时的作用。

这样一步步从暴力到优化，你应该能清晰理解「接雨水」的各种解法的来龙去脉。需要我进一步解释某个细节吗？