AcWing 1574. 接雨水
原题链接
简单
作者:
自说i
,
2024-01-21 12:18:16
,
所有人可见
,
阅读 35
单调栈
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+3;
int stk[N],a[N],maxH,ans,n,top;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
while(top&&a[stk[top]]<=a[i])//维护单调递减的单调栈,到达高的时候出栈
//,把栈顶补平到上一个高度;
{
int loc=stk[top];
top--;
if(top)//如果top现在已经到栈底了,则没有左边界,不可承装雨水,直接出栈
{
int H=min(a[stk[top]],a[i]);
ans+=(H-a[loc])*(i-stk[top]-1);
}
}
stk[++top]=i;
}
cout<<ans;
}