今日学习记录
1. 42. 接雨水
关键词：双指针 栈
问题分析：
核心思路:
间接计算面积法
先是一个奇特的方法,就是计算整体包含雨水的面积,因为就是要把整体填满,填满后,再减去整体就是空缺的雨水了
int trap(vector<int>& height) {
int n = height.size();
int left = 0,right = n-1;
int sum = reduce(height.begin(),height.end(),0);
int h = 1;
int ans = 0;
while(left<=right){
if(height[left]>=h&&height[right]>=h){
ans += (right-left+1);
h++;
}
if(height[left]<h) left++;
if(height[right]<h) right--;
}
return ans-sum;
}最大前后缀
这个接雨水就是类似一个碗来装水,计算每个位置上能装多少水,就看该位置的前面的最大值和后面的最大值的最小值就行,所以计算前缀和后缀最大值就行
int trap(vector<int>& height) {
int n = height.size();
vector<int> pre_mx(n);
vector<int> suf_mx(n);
pre_mx[0] = height[0];
for(int i = 1;i<n;i++){
pre_mx[i] = max(pre_mx[i-1],height[i]);
}
suf_mx[n-1] = height[n-1];
for(int i = n-2;i>=0;i--){
suf_mx[i] = max(suf_mx[i+1],height[i]);
}
int ans = 0;
for(int i = 0;i<n;i++){
ans += min(pre_mx[i],suf_mx[i])-height[i];
}
return ans;
}相向双指针
接雨水的经典解法,也是最优解
int trap(vector<int>& height) {
int n = height.size();
int pre = 0,suf = 0;
int ans = 0;
int left = 0,right = n-1;
while(left<right){
pre = max(pre,height[left]);
suf = max(suf,height[right]);
ans += pre<suf?pre-height[left++]:suf-height[right--];
}
return ans;
}单调栈
不直接记录左端点,而是计算该点之前的一个数,进行面积范围的计算 注意 while 中<=,这样能省去重复元素的空间
int trap(vector<int>& height) {
int ans = 0;
stack<int> s;
for(int i = 0;i<height.size();i++){
int h = height[i];
while(!s.empty()&&height[s.top()]<=h){
int bt = height[s.top()];
s.pop();
if(s.empty()) break;
int left = s.top();
int ht = min(h,height[left])-bt;
ans += ht*(i-left-1);
}
s.push(i);
}
return ans;
}学到的点：
- 双指针
- 栈