题解 | 栈和排序

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm> // for std::max
using namespace std;

void fast_io()//提速
{
    ios_base::sync_with_stdio(false);
    //解耦C和C++的I/O，使得cin与cout的速度与scanf和printf相近
    cin.tie(NULL);
    //解除cin与cout的绑定
    cout.tie(NULL);
    //解除cout与其它流的绑定
}
int main()
{
    fast_io();

    int n;
    scanf("%d",&n);

    vector<int> p(n);
    for(int j=0;j<n;j++)
        scanf("%d",&p[j]);
    
    vector<int> next_greater(n);//存储从p[i]到p[n-1]的最大数
    next_greater[n-1]=p[n-1];
    for(int i=n-2;i>=0;i--)
    {
        next_greater[i]=max(next_greater[i+1],p[i]);
    }

    stack<int>s;
    vector<int>result;
    int i=0;//遍历p

    while(i<n||!s.empty())
    {
        if(!s.empty()&&(i>=n||s.top()>next_greater[i]))
        //贪心：若栈顶元素大于后面所有元素，则出栈，否则入栈。
        {
            result.push_back(s.top());
            s.pop();
        }
        else
        {
            s.push(p[i]);
            i++;
        }
    }
    //打印
    for(int k=0;k<result.size();k++)
    {
        if(k>0)
            printf(" ");
        printf("%d",result[k]);
    }


}