用栈的假排序

链接：https://ac.nowcoder.com/acm/problem/14893
来源：牛客网

给你一个1->n的排列和一个栈，入栈顺序给定
你要在不打乱入栈顺序的情况下，对数组进行从大到小排序
当无法完全排序时，请输出字典序最大的出栈序列

用例

输入
5
2 1 5 3 4

输出
5 4 3 1 2

一开始感觉好难，又要排序又不是全排，只能看题解了，脑子搓，看了挺久才明白并且理解博主代码意思，

其实就是按照栈的“先进后出”的原则，就从后面比大小，就是看i到n的数组里最大值，如果a[i]>maxni+1就先出栈，不然排序更混乱，然后就🆗了；

#include <stdio.h>
const int N=1e6+2;
int n,a[N], maxn[N],sta[N];

int max(int x,int y)
{
     if(x>y)
         return x;
    else return y;
}
int main()
{
    int top=0;
    scanf("%d",&n);
    int i;
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=n;i;--i)
        maxn[i]=max(maxn[i+1],a[i]);
    for(int i=0;i<n;++i)
    {
        sta[++top]=a[i];
        while(top&&sta[top]>maxn[i+1])
        {
            printf("%d ",sta[top--]);
        }
    }
}