接雨水（Trapping Rain Water）
这是力扣第 42 题，经典中的经典。先明确问题：给定一个数组表示柱子高度，计算能接多少雨水。
核心思路：每根柱子能接多少水？
对于位置 i，它能接的水量取决于：
它左边最高柱子 和 右边最高柱子 中，较矮的那个，减去自身高度。
water[i] = max(0, min(leftMax[i], rightMax[i]) - height[i])这是所有解法的共同本质，区别只在于怎么求 leftMax 和 rightMax。
解法一：预处理数组（空间 O(n)，时间 O(n)）
先分别算好每个位置的左最大和右最大，再遍历一遍求和。
python
def trap(height):
n = len(height)
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])
return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))思路清晰，但用了额外空间。
解法二：双指针（空间 O(1)，时间 O(n)）⭐ 最优
不预处理数组，用双指针从两端向中间收缩，边走边维护左右最大值。
python
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0
ans = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
ans += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
ans += right_max - height[right]
right -= 1
return ans为什么这样是对的？ 关键在于：
当 height[left] < height[right] 时，左边较矮，决定左侧积水的瓶颈是 left_max，不需要管右边到底有多高（反正右边一定 ≥ 当前 height[right] > height[left]）——右边已经够高了，左边能接多少水只由 left_max 决定，所以可以放心结算左侧。
解法三：单调栈（另一种思路）
按横向计算每层的水，用栈维护一个单调递减序列，遇到比栈顶高的柱子时，弹出结算。代码稍复杂，时间和空间均 O(n)，不如双指针优雅，但理解它有助于处理类似的”柱状图”系列题。
三种解法对比
| 解法 | 时间 | 空间 | 推荐指数 |
|---|---|---|---|
| 预处理数组 | O(n) | O(n) | ★★★★ 入门首选 |
| 双指针 | O(n) | O(1) | ★★★★★ 面试最优 |
| 单调栈 | O(n) | O(n) | ★★★ 拓展思维 |
面试建议
先讲”每个位置能接多少水 = min(左最大, 右最大) - 自身高度“建立直觉，然后直接给出双指针解法，并解释为什么能省掉预处理数组——这个推理过程最能体现理解深度。