题解 | 接雨水问题

class Solution {
public:
    long long maxWater(vector<int>& arr) {
        if (arr.size() <= 2) return 0;
        
        int left = 0, right = arr.size() - 1;
        int left_max = 0, right_max = 0;
        long long result = 0;
        
        while (left < right) {
            // 更新左右两边的最大高度
            left_max = max(left_max, arr[left]);
            right_max = max(right_max, arr[right]);
            
            // 移动较矮的一侧指针
            if (arr[left] < arr[right]) {
                // 左边较矮，计算左边能接的雨水
                result += left_max - arr[left];
                left++;
            } else {
                // 右边较矮，计算右边能接的雨水
                result += right_max - arr[right];
                right--;
            }
        }
        
        return result;
    }
};

思路：

1. 使用左右两个指针，分别从数组两端开始向中间移动
2. 维护左右两边的最大高度
3. 每次移动高度较小的一侧的指针，因为接雨水的量由较矮的一边决定
4. 计算当前位置能接的雨水量
5. 双指针方法的优雅之处就在于它充分利用了"短板效应"，每次只处理确定能接雨水的位置，避免了复杂的全局计算。这正是算法设计中"局部最优导致全局最优"的经典体现。