题解 | 栈和排序

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int p[2000006];//将数组定义在主函数外，节省内存

//本题实际上是希望考生先将数据按从大到小输出，再将数据逆向输出
int main() {
    int n{};//定义最大数n
    cin>>n;
    getchar();//释放回车符号
    for(int i=0;i<n;i++)//将n个数据写入数组p
    {
        cin>>p[i];
    }

    stack<long> a;
    vector<long> c;//定义栈a和序列c
    int k=n;//这里是需要一个数来记录1~n中的最大降序排列
    for(int i=0;i<n;i++)
    {
        a.push(p[i]);//先将p中的数据挨个入栈
        if(a.top()==k)//如果碰到最大数
        {
            c.push_back(a.top());//将最大数push进序列c
            k--;//最大数的值减一
            a.pop();//原最大数出栈
            continue;//似乎可有可无，此处保留
        }

        
    }   

    for(int i=0;i<c.size();i++)//c中的数据此时是降序排列，直接输出
    {
        cout<<c[i]<<" ";
    }

    while(!a.empty())
    {
        cout<<a.top();//再将栈顶数据挨个输出
        a.pop();
        if(!a.empty())//对空格的处理
        cout<<" ";
    }
    





    return 0;
}
// 64 位输出请用 printf("%lld")