yicong@algo: ~/code/02-two-pointers/0042-trapping-rain-water.cpp

yicong@algo:~/code/02-two-pointers$ cat 0042-trapping-rain-water.cpp

42. 接雨水

困难 双指针 题目 ↗ 源码 ↗

// 思路

每个位置的水量 = min(左侧最高, 右侧最高) - height[i]。 版本一 trap:双指针从两端向中间收,leftMax/rightMax 分别维护两侧已见过的最高柱子; 每轮先更新当前柱子,再比较 leftMax 与 rightMax,谁小就结算谁并移动该侧指针。 版本二 trapByScan(原版):leftMax 增量维护,rightMax 在 x 越过旧最大值下标时重新扫描后缀。

// 时间复杂度

版本一 O(n);版本二最坏 O(n^2)(严格递减时每个 x 都重扫后缀),递增时 O(n)

// 空间复杂度

O(1),两个版本都只用了常数个变量

// 易错点

1) 双指针必须先更新 leftMax/rightMax 再加水,否则新高柱会算出负数 2) 双指针循环用 left < right,相等时走哪边都可以 3) 版本二中 x > right 表示旧的后缀最大值已移出 [x, n-1],此时必须重算 4) 题目保证高度非负,leftMax/rightMax 初值取 0 才是安全的

// 面试口述要点

leftMax < rightMax 时,l 的真实右边界至少是 rightMax,比 leftMax 大, 所以 min 由 leftMax 决定,可以立即结算 l;右侧对称。版本二是按列公式的直接实现, 正确但最坏 O(n^2),面试提交用双指针版。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // 版本一:双指针 O(n)。左右各维护一个最大值,两指针向中间收。
    int trap(vector<int>& height) {
        int left = 0;
        int right = (int)height.size() - 1;
        int leftMax = 0;
        int rightMax = 0;
        int ans = 0;

        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);

            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }

    // 版本二(原版):按列计算,右侧最大值每次重新扫描后缀,最坏 O(n^2)。
    int trapByScan(vector<int>& height) {
        int ans = 0;
        int left = 0;
        int right = 0;
        for (int x = 1; x < (int)height.size() - 1; x++){
            if (height[x] >= height[left]) left = x;
            if (x > right){
                right = height.size() - 1;
                for (int i = height.size() - 1; i >= x; i--)
                    if(height[right] < height[i]) 
                        right = i;
            }
            ans += min(height[left], height[right]) - height[x];
        }
        return ans;
    }
};

// 本地测试:输入 n,然后 n 个高度;输出能接的雨水总量
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> height(n);
    for (int& x : height) cin >> x;

    cout << Solution().trap(height) << '\n';
    return 0;
}