力扣面试17.21题解：双指针算法高效求解接雨水问题（含代码注释与优化思路）
一、题目解读
力扣面试17.21题（接雨水问题）要求计算给定高度数组中，凹槽结构能容纳的雨水总量。例如，数组[0,1,0,2,1,0,1,3,2,1,2,1]形成的凹槽可积水6单位（可视化后凹陷部分水量）。核心难点在于高效遍历数组，精准计算各位置积水，避免冗余计算。
二、解题思路
1. 核心原理：从数组左右两端同时向内逼近，实时记录两侧最大高度。积水由“短板效应”决定——每次移动较低侧指针，利用另一侧的最大高度作为“虚拟墙”计算当前位置水量。
2. 优势：避免全局遍历与栈空间消耗，时间复杂度降至O(n)，空间O(1)。
三、解题步骤
1. 初始化：
左指针left=0，右指针right=height.size()-1；
两侧最大高度left_max=0, right_max=0，水量water=0。
2. 循环逼近：
更新当前两侧最大高度：left_max = max(left_max, height[left]), right_max = max(right_max, height[right])；
若height[left] < height[right]（左低右高），则左移指针：积水为left_max - height[left]（虚拟右墙与当前高度的差），left++；反之右移right--。
3. 终止条件：left >= right时所有积水计算完毕。
四、代码与注释
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
if (height.empty()) return 0; // 空数组特判
int left = 0, right = height.size() - 1;
int left_max = 0, right_max = 0;
int water = 0;
while (left < right) {
// 更新左右最大值
left_max = max(left_max, height[left]); // 动态维护左墙高度
right_max = max(right_max, height[right]); // 动态维护右墙高度
// 较小的一边决定当前能存的水量
if (height[left] < height[right]) {
water += left_max - height[left]; // 左低时，积水=左墙高度-当前高度
left++; // 左指针内移
} else {
water += right_max - height[right]; // 右低同理
right--;
}
}
return water;
}
};注释解析：关键步骤通过“动态维护虚拟墙高度”与“短板移动”实现水量累加，避免全局搜索。
五、总结
1. 算法亮点：
○ 双指针+动态更新策略，将二维积水问题转化为线性遍历，降低复杂度。
○ 代码简洁，无额外空间开销，适用于大规模数据场景。
2. 优化方向：
3. 应用场景：该思想适用于“区间最值决定结果”的类似问题，如柱状图最大面积计算等。
原创内容 转载请注明出处
