1. 接雨水问题解析与双指针解法实战

这道题是LeetCode上经典的hard级别题目，考察对数组和双指针算法的掌握程度。我第一次遇到这个问题时，花了整整一个下午才理解透彻。现在让我们一起来拆解这个看似简单实则精妙的算法问题。

2. 问题本质与核心思路

2.1 问题重述与可视化理解

给定n个非负整数表示柱子的高度，计算这些柱子排列后能接住的雨水总量。举个形象的例子：就像是在凹凸不平的地面上摆放不同高度的积木，下雨后积木之间会积攒多少水。

以示例1为例：

高度数组：[0,1,0,2,1,0,1,3,2,1,2,1] 可视化表示： ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

蓝色区域即为可接住的雨水，总计6个单位。

2.2 关键观察点

1. 雨水的形成条件：两侧存在比当前柱子高的边界
2. 单个柱子的储水量：min(左侧最高，右侧最高) - 当前高度
3. 边界条件：最左和最右的柱子不能储水

3. 双指针解法详解

3.1 算法思路

这是最优美的解法之一，时间复杂度O(n)，空间复杂度O(1)。核心思想是：

1. 维护左右指针和左右最大值
2. 每次移动较小值那边的指针
3. 根据左右最大值的较小值计算当前储水量

class Solution { public: int trap(vector<int>& height) { int ans = 0; int left = 0, right = height.size() - 1; int leftMax = 0, rightMax = 0; while (left < right) { leftMax = max(leftMax, height[left]); rightMax = max(rightMax, height[right]); if (height[left] < height[right]) { ans += leftMax - height[left]; ++left; } else { ans += rightMax - height[right]; --right; } } return ans; } };

3.2 分步解析

1. 初始化：左右指针分别指向数组首尾，左右最大值初始为0
2. 循环条件：左指针小于右指针
3. 更新最大值：比较并更新左右指针所指的当前最大值
4. 移动指针：总是移动高度较小的一侧的指针
5. 计算储水量：用当前侧的最大值减去当前高度

关键点：为什么可以这样计算？因为储水量由较矮的一侧决定，我们总是处理较矮的一侧，确保另一侧有足够高的"墙"。

4. 算法正确性证明

4.1 为什么移动较小值指针？

假设height[left] < height[right]：

• 此时leftMax <= rightMax（因为leftMax是left左侧的最大值）
• 所以储水量由leftMax决定
• 可以安全地计算left位置的储水量并移动指针

反之亦然。这个策略确保了我们在计算时，另一侧总有足够高的边界。

4.2 边界情况处理

• 单调递增/递减序列：不会储水
• 所有柱子等高：不会储水
• 单峰/双峰情况：能正确处理

5. 复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只使用了常数个额外变量

6. 其他解法对比

6.1 暴力法（不推荐）

对每个柱子，向左右扫描找到最大值：

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

int trap(vector<int>& height) { int ans = 0; for (int i = 0; i < height.size(); ++i) { int left_max = 0, right_max = 0; for (int j = i; j >= 0; --j) left_max = max(left_max, height[j]); for (int j = i; j < height.size(); ++j) right_max = max(right_max, height[j]); ans += min(left_max, right_max) - height[i]; } return ans; }

6.2 动态规划法

预处理左右最大值数组：

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

int trap(vector<int>& height) { if (height.empty()) return 0; int n = height.size(); vector<int> left_max(n), right_max(n); left_max[0] = height[0]; for (int i = 1; i < n; ++i) left_max[i] = max(left_max[i-1], height[i]); right_max[n-1] = height[n-1]; for (int i = n-2; i >= 0; --i) right_max[i] = max(right_max[i+1], height[i]); int ans = 0; for (int i = 0; i < n; ++i) ans += min(left_max[i], right_max[i]) - height[i]; return ans; }

6.3 单调栈解法

利用栈维护递减序列：

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

int trap(vector<int>& height) { stack<int> st; int ans = 0; for (int i = 0; i < height.size(); ++i) { while (!st.empty() && height[i] > height[st.top()]) { int top = st.top(); st.pop(); if (st.empty()) break; int distance = i - st.top() - 1; int bounded_height = min(height[i], height[st.top()]) - height[top]; ans += distance * bounded_height; } st.push(i); } return ans; }

7. 实际编码中的注意事项

1. 边界检查：空数组或单元素数组直接返回0
2. 指针移动条件：严格使用height[left]和height[right]比较
3. 最大值更新：必须在指针移动前更新
4. 整数溢出：虽然题目约束了数据范围，但在其他场景要考虑

8. 常见错误与调试技巧

8.1 典型错误案例

错误实现1：忘记更新最大值

// 错误示范 if (height[left] < height[right]) { ans += leftMax - height[left]; // leftMax可能不是最新的 ++left; }

错误实现2：指针移动条件错误

// 错误示范 if (leftMax < rightMax) { // 应该比较height[left]和height[right] ans += leftMax - height[left]; ++left; }

8.2 调试建议

1. 打印中间变量：在循环中打印left, right, leftMax, rightMax, ans
2. 小规模测试：先用示例1手动模拟算法流程
3. 边界测试：测试空数组、全0数组、单调数组等特殊情况

9. 算法优化与变种

9.1 代码简化版

int trap(vector<int>& height) { int l = 0, r = height.size()-1, lmax = 0, rmax = 0, res = 0; while (l < r) { lmax = max(lmax, height[l]); rmax = max(rmax, height[r]); res += height[l] < height[r] ? lmax - height[l++] : rmax - height[r--]; } return res; }

9.2 三维接雨水问题

这是二维问题的扩展，可以使用类似的思路但更复杂。感兴趣的读者可以尝试LeetCode 407题。

10. 面试中的应用技巧

1. 先阐述暴力解法，再优化
2. 画图解释双指针移动的原理
3. 讨论时间/空间复杂度的权衡
4. 准备相关问题的变种（如三维接雨水）

我在面试候选人时，发现能清晰解释这个算法原理的人通常对指针操作有深刻理解。建议在理解的基础上记忆这个优美的解法，它展示了如何通过巧妙的指针移动来优化空间复杂度。