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

fiwhgikbl

一、问题描述

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

二、算法核心思想

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

• 使用左右指针从两端向中间移动
• 维护左右两边的**值
• 根据较小的一边计算当前能接的雨水量
• 移动较小值的指针继续计算
  
  

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

1. #include <vector>
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. class Solution {
   
6. public:
   
7.     int trap(vector<int>& height) {
   
8.         if (height.empty()) return 0;  // 空数组直接返回0
   
9.         
   
10.         int left = 0, right = height.size() - 1;  // 初始化左右指针
    
11.         int left_max = 0, right_max = 0;  // 初始化左右**值
    
12.         int water = 0;  // 初始化雨水总量
    
13.         
    
14.         while (left < right) {
    
15.             // 更新左右**值
    
16.             left_max = max(left_max, height[left]);
    
17.             right_max = max(right_max, height[right]);
    
18.             
    
19.             // 较小的一边决定当前能存的水量
    
20.             if (height[left] < height[right]) {
    
21.                 water += left_max - height[left];  // 计算左边能接的雨水
    
22.                 left++;  // 移动左指针
    
23.             } else {
    
24.                 water += right_max - height[right];  // 计算右边能接的雨水
    
25.                 right--;  // 移动右指针
    
26.             }
    
27.         }
    
28.         
    
29.         return water;  // 返回总雨水量
    
30.     }
    
31. };

复制代码

四、算法分步解析

• 初始化阶段：
  
  
  • 检查输入数组是否为空
  • 设置左右指针和**值变量
  • 初始化雨水总量为0
    
    
• 双指针移动阶段：
  
  
  • 更新左右两边的**值
  • 比较当前左右指针指向的高度
  • 根据较小的一边计算雨水量
  • 移动较小值对应的指针
    
    
• 结果返回：
  
  
  • 当左右指针相遇时结束循环
  • 返回累计的雨水总量
    
    

五、常见误区与调试技巧

• 忘记处理空数组的特殊情况
• 错误计算左右**值
• 指针移动条件判断错误
• 雨水量计算公式错误
  
  

来源：力扣面试17.21题解：接雨水问题的双指针**解