栈和排序 题解

一个简单的贪心做法（已通过@7QQQQQQQ大佬的hack数据）

我们设maxe[i]表示i-n的元素的最大值。

那么，我们假设，当前栈顶的元素比maxe[i+1]大（最近入栈的是第i个元素），那么，不难发现，如果我们当前元素不出栈的话，之后如果有元素入栈，那么最后出栈的字典序一定会小于当前元素出栈的字典序。于是按照这个策略模拟即可~

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2;
int a[N],maxe[N],sta[N],top;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=n;i;--i){
        maxe[i]=max(maxe[i+1],a[i]);
    }
    for(int i=1;i<=n;++i){
        sta[++top]=a[i];
        while(top&&sta[top]>maxe[i+1]){//因为maxe[n+1]=0,所以最后一定会把栈弹空
            printf("%d ",sta[top--]);
        }
    }
    return 0;
}