AcWing 1574. 接雨水o(n)题解
原题链接
困难
//算法时间复杂度应该是o(n)
//同时需要设计算法的边界条件
#include <iostream>
using namespace std;
int n;
const int N = 1e5 + 10;
int h[N],l[N],r[N],l_left[N],r_right[N];
int main(){
//传入相关数据
cin >> n;
l[0] = r[n + 1] = -1;
for(int i = 1; i <= n; i++) scanf("%d", &h[i]);
//l为以当前点结尾的左边最大值
//l_left是当前点左边大于当前点的最大值,不存在则为0
for(int i = 1; i <= n; i++){
l[i] = max(l[i - 1],h[i]);
l_left[i] = l[i] > h[i] ? l[i] : 0;
}
//r为以当前点结尾的右边最大值
//r_right是当前点右边大于当前点的最大值,不存在则为0
for(int i = n; i >= 1; i--){
r[i] = max(r[i + 1],h[i]);
r_right[i] = r[i] > h[i] ? r[i] : 0;
}
//遍历计算当前点可以接到的最大雨水数量
//每个点可以接到“左右较低边 减去 当前点值”数量的雨水
int res = 0;
for(int i = 1; i <= n; i ++){
if(l_left[i] && r_right[i]){
int size = min(l_left[i],r_right[i]);
res += size - h[i];
}
}
printf("%d",res);
return 0;
}