好的，我们这次来详细讲解 「接雨水」 这个经典题目（LeetCode 42. Trapping Rain Water）。
它和「盛最多水的容器」有点像，但核心逻辑不同，更考验对数组结构的理解。

1. 题目描述

给定 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

2. 问题分析

2.1 核心思路

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

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

并且如果这个值小于 0，则取 0（即水量非负）。

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

为什么？
因为雨水高度由左右两边最高柱子的较矮者（木桶原理）决定，再减去当前柱子的高度（如果有柱子就占用了空间）。

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])，从右往左遍历

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

示例：
height = [0,1,0,2,1,0,1,3,2,1,2,1]

1. 计算 leftMax:

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

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

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

3. 计算每个位置水量：

   • 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 ✅

时间复杂度：O(n)
空间复杂度：O(n)
已经比暴力法好很多。

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

我们能否不用两个数组，而用两个指针边走边计算？

思路：

• 用 left 和 right 指针从两端向中间移动
• 维护 leftMax 和 rightMax 表示当前遇到的左右最高值
• 每次移动较矮那边的指针，因为水量是由较矮的一边决定的

步骤：

1. 初始化 left=0, right=n-1, leftMax=0, rightMax=0, ans=0
2. 当 left < right：
   • 如果 height[left] < height[right]：
     • 说明左边最大值决定此处水量（因为右边有更高的 rightMax 保证）
     • 如果 height[left] >= leftMax，更新 leftMax
     • 否则，ans += leftMax - height[left]
     • left++
   • 否则（height[left] >= height[right]）：
     • 说明右边最大值决定水量
     • 如果 height[right] >= rightMax，更新 rightMax
     • 否则，ans += rightMax - height[right]
     • right--

为什么可行？
因为对于某个指针指向的位置，只要另一侧有更高的边界，当前侧的最高值就是有效的最小边界，可以直接算水。

示例（简略推演）：
height = [0,1,0,2,1,0,1,3,2,1,2,1]

• left=0, right=11, leftMax=0, rightMax=0
• height[0]=0 < height[11]=1 → 处理左指针：
  • height[0]=0 >= leftMax=0? 是，更新 leftMax=0
  • left=1
• height[1]=1 < height[11]=1? 相等，走右边分支（按>=算）：
  • 处理右指针：height[11]=1 >= rightMax=0? 是，更新 rightMax=1
  • right=10
• height[1]=1 < height[10]=2? 是，处理左指针：
  • height[1]=1 >= leftMax=0? 是，更新 leftMax=1
  • left=2
• height[2]=0 < height[10]=2? 是，处理左指针：
  • height[2]=0 >= leftMax=1? 否，ans += 1-0=1
  • left=3
• 继续... 最终 ans=6

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

4. 代码实现（双指针法）

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. 总结

• 关键公式：每个位置水量 = min(左边最高, 右边最高) − 当前高度
• 暴力法：O(n²) 超时，但直观
• 动态规划：O(n) 时间与空间，可靠
• 双指针：O(n) 时间，O(1) 空间，最优解

这个题目是面试高频题，理解“由较矮边界决定当前水量”是核心。