LeetCode 42 接雨水 - 双指针解法
🔴 困难
https://leetcode.cn/problems/trapping-rain-water/description/
逆天思路: 每个位置能接住的雨水取决于左边也取决于右边， 是左边所有和右边所有最大值的最小值.
可以先遍历一下当前位置左边的最大值， 再找到右边的最大值，取最小值即可。
class Solution {
public:
int trap(vector<int>& height) {
vector<int> pre;
int pre_height = 0;
for(int i = 0;i<height.size();i++){
pre_height = max(pre_height,height[i]);
pre.push_back(pre_height);
}
vector<int> back;
int back_height = 0;
for(int i = height.size()-1;i>=0;i--){
back_height = max(back_height,height[i]);
back.insert(back.begin(),back_height);
}
int ans = 0;
for(int i = 0;i<height.size();i++){
int count = min(pre[i],back[i]);
if(count>height[i]){
ans+=count-height[i];
}
}
return ans;
}
};
也可以使用双指针
一开始两边的挡板都是0， 正如最外面的这个柱子不能盛水一样; 如果左边挡板小， 那么也不一定能盛水， 要算 左边挡板-这个位置主子的高度， 还要及时更新左边挡板的高度。
class Solution {
public:
int trap(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int pre_max = 0;
int last_max = 0;
int ans = 0;
while (left <= right) {
//一开始就认准 最外面的两个柱子,初始挡板都是0,
if (pre_max < last_max) {
if (pre_max - height[left] > 0) {
ans += (pre_max - height[left]);
}
pre_max = max(pre_max, height[left]);
left++;
} else {
//如果右边的挡板小, 由右挡板计算盛水值,
if (last_max - height[right] > 0) {
ans += (last_max - height[right]);
}
//不论能否盛水, 都要更新挡板的大小.
last_max = max(last_max, height[right]);
right--;
}
}
return ans;
}
};
要点总结
某一位置能盛的水既取决于左边最值， 也取决于右边最值。