链接: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--]);
        }
    }
}