力扣面试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. 应用场景：该思想适用于“区间最值决定结果”的类似问题，如柱状图最大面积计算等。