P5788 【模板】单调栈

链接：Miku

单调栈模板终于不是一堆蓝题了！！！！！！！！！！！！

单调栈，就是单调的栈，栈内元素都是单调的。

题目要求我们求出来第一个比i大的元素的下标，那么我们就可以用一个递减单调栈解决。

每一个元素入栈时，和栈顶比较一下，如果比他大，那他一定是第一个比它大的。所以说记录弹出就行。

重复这个过程，知道栈空了或者说比栈顶小了，再把新元素放进去。

#include<iostream>
#include<stack>
#include<cstdio>
using namespace std;
long long  n;
//stack <long long > s;
long long  ans[4000001];
long long  x;
struct s{
    long long  v;
    long long  num;
}now;;
stack <s> ss;
int  main(){
    cin>>n;
    for(long long  i=1;i<=n;++i){
        scanf("%d",&now.v);
        now.num=i;
        if(ss.empty()){
            ss.push(now);
            continue;
        }
        while(!ss.empty()&&ss.top().v<now.v){
            ans[ss.top().num]=i;
            ss.pop();
        }
        ss.push(now);
    }
    for(long long  i=1;i<=n;++i){
        printf("%d ",ans[i]);
    }
    return 0;
}

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论