AcWing 1574. 接雨水
原题链接
简单
作者:
bunny_4
,
2025-06-10 09:55:45
· 辽宁
,
所有人可见
,
阅读 1
#include <iostream>
using namespace std;
const int N=1e5+10;
int stk[N],h[N]; // stk为单调栈存的是下标 h为记录的高度
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>h[i];
int tt=-1,res=0; // tt为栈顶指针
for (int i=0;i<n;i++)
{
int last =0; // last为上一个的高度
while(tt>=0 && h[stk[tt]]<h[i]) // 如果当前遍历的元素比栈顶元素大,那么代表是有可接水的区间的
{
res+=(h[stk[tt]]-last)*(i-stk[tt]-1);
last=h[stk[tt]];
tt--;
}
if (tt>=0)res+=(h[i]-last)*(i-stk[tt]-1); // z注意此处的为h[i]而不是h[stk[tt]l 因为要用的是比较矮的来计算
stk[++tt]=i;
}
cout<<res<<endl;
return 0;
}