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;
}