力扣面试17.21题解：接雨水问题的双指针最优解

一、问题描述

给定n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

二、算法核心思想

本解决方案采用双指针法：

1. 使用左右指针从两端向中间移动

2. 维护左右两边的最大值

3. 根据较小的一边计算当前能接的雨水量

4. 移动较小值的指针继续计算

三、完整代码实现（带详细注释）

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;  // 空数组直接返回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. 初始化阶段：

• 检查输入数组是否为空

• 设置左右指针和最大值变量

• 初始化雨水总量为0

2. 双指针移动阶段：

• 更新左右两边的最大值

• 比较当前左右指针指向的高度

• 根据较小的一边计算雨水量

• 移动较小值对应的指针

3. 结果返回：

• 当左右指针相遇时结束循环

• 返回累计的雨水总量

五、常见误区与调试技巧

1. 忘记处理空数组的特殊情况

2. 错误计算左右最大值

3. 指针移动条件判断错误

4. 雨水量计算公式错误

来源：力扣题解