NC14893栈和排序

原题链接：传送门

思路：其实就是模拟栈的排序顺序，我们让每个数按照他的顺序进栈，在进栈的过程中用一个cnt=n来标记，当前进栈的数满足s.top==cnt时，说明此时已达到了出栈条件，（因为是从大到小排序的）所以我们让当前的数出栈，（然后cnt--，继续寻找下一个出栈条件）当所有的数都进栈后，剩下还没出栈的我们让他所有的都出栈，这就可以满足字典序最大的出栈序列

#include<iostream>
#include<stack>

using namespace std;
const int N=1e6+5;
int a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
    int cnt=n;
    stack<int>s;
    for(int i=0;i<n;i++)
    {
        if(s.empty())//当前空栈直接进栈，同时判断是否满足出栈条件
        {
            s.push(a[i]);
            if(s.top()==cnt)
            {
                printf("%d ",s.top());
                s.pop();
                cnt--;
            }
        }
        else if(s.top()==cnt)//不空的栈判断是否满足条件
        {
            printf("%d ",s.top());
            s.pop();
            cnt--;
            s.push(a[i]);
        }
        else s.push(a[i]);//不满足的条件记得继续入栈
    }    
    while(!s.empty())//最后把未出栈的出栈
    {
        printf("%d ",s.top());
        s.pop(); 
    }
    return 0;
}