AcWing 830. 单调栈(找到每个数后面第一个比它大的数)
原题链接
简单
作者:
挂科就改名
,
2022-01-26 16:31:21
,
所有人可见
,
阅读 543
思考:如何求后面第一个比它大的数呢?!
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int stk[N],s[N],m[N],tt; //根据y总讲的找到前面第一个比它小的数的思路来想,可以先把这些数存在一个数组中然后反向列举,就转化为了找到前面第一个比它大的数,把这些数存到一个数组中,最后再反向输出就可以了,因此需要两个中间数组
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&s[i]);
for(int i=n;i>=1;i--)
{
while(tt&&stk[tt]<=s[i]) tt--; //因为要找到第一个比它大的数,故此处应该为单调递增,如果前面的数小于新录入的数,则删除前面的数
if(tt) m[i]=stk[tt];
else m[i]=-1;
stk[++tt]=s[i];
}
for(int i=1;i<=n;i++) printf("%d",m[i]);
return 0;
}
lihai
6