好的，我们这次来详细讲解 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 个单位的雨水（蓝色部分表示雨水）。

2. 问题理解

想象这些柱子围成的凹槽能存水，水的高度取决于左右两侧的最高柱子中的较小值（木桶效应）。

对于位置 i，它能接的雨水量等于：

\[\text{water}[i] = \min(\text{leftMax}[i], \text{rightMax}[i]) - \text{height}[i] \]

其中：

• leftMax[i] = i 左侧（包括 i）的最高柱子高度
• rightMax[i] = i 右侧（包括 i）的最高柱子高度

如果这个值小于 0，则取 0（即柱子比水面高时接不到水）。

3. 思路演进

3.1 暴力法（直接按定义）

对每个位置 i：

• 向左扫描找到左边最大值
• 向右扫描找到右边最大值
• 计算积水量

时间复杂度：O(n²)
空间复杂度：O(1)
会超时，但有助于理解。

3.2 动态规划（预处理数组）

我们可以预先计算好每个位置的 leftMax 和 rightMax。

• leftMax[i] = max(leftMax[i-1], height[i])，从左往右遍历
• rightMax[i] = max(rightMax[i+1], height[i])，从右往左遍历

然后遍历一次计算总雨水量。

时间复杂度：O(n)
空间复杂度：O(n)

步骤演示（示例 height = [0,1,0,2,1,0,1,3,2,1,2,1]）：

1. 计算 leftMax：

   • i=0: leftMax[0] = 0
   • i=1: leftMax[1] = max(0,1) = 1
   • i=2: leftMax[2] = max(1,0) = 1
   • i=3: leftMax[3] = max(1,2) = 2
   • ... 得到 leftMax = [0,1,1,2,2,2,2,3,3,3,3,3]

2. 计算 rightMax（从右往左）：

   • i=11: rightMax[11] = 1
   • i=10: rightMax[10] = max(1,2) = 2
   • i=9: rightMax[9] = max(2,1) = 2
   • ... 得到 rightMax = [3,3,3,3,3,3,3,3,2,2,2,1]

3. 计算每个位置雨水（min(leftMax,rightMax) - height）：

   • i=0: min(0,3)-0=0
   • i=1: min(1,3)-1=0
   • i=2: min(1,3)-0=1
   • i=3: min(2,3)-2=0
   • i=4: min(2,3)-1=1
   • i=5: min(2,3)-0=2
   • i=6: min(2,3)-1=1
   • i=7: min(3,3)-3=0
   • i=8: min(3,2)-2=0
   • i=9: min(3,2)-1=1
   • i=10: min(3,2)-2=0
   • i=11: min(3,1)-1=0

   总和 = 0+0+1+0+1+2+1+0+0+1+0+0 = 6 ✅

3.3 双指针法（空间优化到 O(1)）

我们能否不用数组存 leftMax 和 rightMax？
可以，用两个指针 left 和 right 从两端向中间移动，并维护 leftMax 和 rightMax 变量。

核心思想：
对于某个位置，我们只需要知道左右最大值中的较小值。

• 如果 leftMax < rightMax，那么左边最大值是瓶颈，可以计算 left 位置的雨水，然后左指针右移
• 否则，右边最大值是瓶颈，计算 right 位置的雨水，右指针左移

算法步骤：

1. left=0, right=n-1, leftMax=0, rightMax=0, ans=0
2. while left <= right:
   • 如果 height[left] < height[right]:
     • 如果 height[left] >= leftMax: 更新 leftMax
     • 否则: ans += leftMax - height[left]
     • left++
   • 否则:
     • 如果 height[right] >= rightMax: 更新 rightMax
     • 否则: ans += rightMax - height[right]
     • right--

为什么可行：
因为当 height[left] < height[right] 时，left 位置的右边最大值肯定 >= height[right]（可能更大），而左边最大值 leftMax 已知，且瓶颈在 leftMax 与 rightMax 的较小值，此时 leftMax <= rightMax 是确定的（因为 height[left] < height[right] 且历史 leftMax 可能更小），所以可以安全地用 leftMax 计算 left 处雨水。

双指针法示例（height = [0,1,0,2,1,0,1,3,2,1,2,1]）：

初始化：left=0, right=11, leftMax=0, rightMax=0, ans=0

1. height[0]=0 < height[11]=1 → 左边计算：

   • height[0]=0 >= leftMax=0? 是 → leftMax=0
   • left=1

2. height[1]=1 < height[11]=1? 否 → 走右边计算：

   • height[11]=1 >= rightMax=0? 是 → rightMax=1
   • right=10

3. height[1]=1 < height[10]=2? 是 → 左边计算：

   • height[1]=1 >= leftMax=0? 是 → leftMax=1
   • left=2

4. height[2]=0 < height[10]=2? 是 → 左边计算：

   • height[2]=0 >= leftMax=1? 否 → ans += 1-0=1
   • left=3

5. height[3]=2 < height[10]=2? 否 → 右边计算：

   • height[10]=2 >= rightMax=1? 是 → rightMax=2
   • right=9

6. height[3]=2 < height[9]=1? 否 → 右边计算：

   • height[9]=1 >= rightMax=2? 否 → ans += 2-1=1
   • right=8

7. height[3]=2 < height[8]=2? 否 → 右边计算：

   • height[8]=2 >= rightMax=2? 是 → rightMax=2
   • right=7

8. height[3]=2 < height[7]=3? 是 → 左边计算：

   • height[3]=2 >= leftMax=1? 是 → leftMax=2
   • left=4

9. height[4]=1 < height[7]=3? 是 → 左边计算：

   • height[4]=1 >= leftMax=2? 否 → ans += 2-1=1
   • left=5

10. height[5]=0 < height[7]=3? 是 → 左边计算：

    • height[5]=0 >= leftMax=2? 否 → ans += 2-0=2
    • left=6

11. height[6]=1 < height[7]=3? 是 → 左边计算：

    • height[6]=1 >= leftMax=2? 否 → ans += 2-1=1
    • left=7

12. left=7, right=7 → height[7]=3 < height[7]=3? 否 → 右边计算：

    • height[7]=3 >= rightMax=2? 是 → rightMax=3
    • right=6

13. left=7 > right=6 → 结束

ans = 1+1+1+2+1 = 6 ✅

4. 代码实现（Python）

def trap(height):
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    leftMax, rightMax = 0, 0
    ans = 0
    
    while left <= right:
        if height[left] < height[right]:
            if height[left] >= leftMax:
                leftMax = height[left]
            else:
                ans += leftMax - height[left]
            left += 1
        else:
            if height[right] >= rightMax:
                rightMax = height[right]
            else:
                ans += rightMax - height[right]
            right -= 1
    
    return ans

5. 复杂度分析

• 时间复杂度：O(n)，一次遍历
• 空间复杂度：O(1)，只用了几个变量

6. 总结

• 核心公式：每个位置雨水 = min(左边最高, 右边最高) - 自身高度
• 暴力法帮助理解，但效率低
• 动态规划法预处理数组，时间 O(n)，空间 O(n)
• 双指针法优化空间到 O(1)，利用左右瓶颈思想，一次遍历完成

这样循序渐进地理解，就能掌握这道经典题目了。