1. 问题背景与核心挑战

接雨水问题是LeetCode上经典的Hard级别算法题（编号42），也是面试高频考点。题目描述如下：给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子能接多少雨水。

实际场景中，这个问题可以类比城市建筑群的雨水收集系统设计。假设有一排高低不齐的建筑，雨水会自然在低洼处积聚。我们需要精确计算这些"天然蓄水池"的总容量。

2. 暴力解法与优化思路

2.1 直观暴力解法

最直接的思路是逐列计算：

1. 遍历每个柱子（除了首尾）
2. 向左找最高柱子left_max
3. 向右找最高柱子right_max
4. 当前柱子积水量为min(left_max, right_max) - height[i]

def trap_brute(height): res = 0 for i in range(1, len(height)-1): left_max = max(height[:i]) right_max = max(height[i+1:]) res += max(0, min(left_max, right_max) - height[i]) return res

时间复杂度O(n²)，空间复杂度O(1)。在LeetCode上会超时。

2.2 动态规划优化

预先存储每个位置的左右最大值：

def trap_dp(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[-1] = height[-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 += max(0, min(left_max[i], right_max[i]) - height[i]) return res

时间复杂度O(n)，空间复杂度O(n)。这是面试中最常考的解法。

3. 最优解：双指针法

3.1 算法原理

通过左右指针向中间移动，实时维护左右最大值：

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

时间复杂度O(n)，空间复杂度O(1)。这是最优解法。

3.2 关键点解析

1. 移动策略：总是移动高度较小的一侧指针
2. 水量计算：基于当前侧的已记录最大值
3. 终止条件：左右指针相遇

4. 变种问题与扩展思考

4.1 三维接雨水问题

当问题扩展到二维平面时（如LeetCode 407），需要使用优先队列（堆）来处理。核心思路是从外围向内收缩，每次处理高度最小的点。

4.2 实际工程应用

1. 城市排水系统设计
2. 地形蓄水能力计算
3. 图像处理中的区域分割

5. 刷题建议与避坑指南

5.1 常见错误

1. 忽略边界条件（空数组或单元素）
2. 水量计算忘记处理负数情况
3. 双指针移动方向错误

5.2 学习路径推荐

1. 先掌握暴力解法理解问题本质
2. 再学习动态规划优化思路
3. 最后攻克双指针最优解
4. 尝试用不同语言实现（Python/Java/C++）

提示：面试时建议先阐述暴力解法，再逐步优化，展示完整的思考过程。直接给出最优解可能适得其反。