AcWing 1574. 接雨水 单调栈
原题链接
困难
作者:
思念是一种病
,
2021-08-20 15:31:44
,
所有人可见
,
阅读 285
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1e5+10;
int h[N];
int stk[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&h[i]);
int res=0;
int tt=-1;
for(int i=0;i<n;i++)
{
int last=0;
while(tt>=0 && h[stk[tt]]<h[i])
{
res+=(i-stk[tt]-1)*(h[stk[tt]]-last);
last=h[stk[tt]];
tt--;
}
if(tt>=0) res+=(i-stk[tt]-1)*(h[i]-last);
stk[++tt]=i;
}
cout<<res<<endl;
return 0;
}