题解 | 栈和排序

#include <iostream>
#include <climits>
using namespace std;

const int N = 1e6 + 10;

int main()
{
    int n = 0;
    int top = 0;
    int a[N];
    int maxe[N];
    int s[N];

    cin >> n;
    getchar();

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    getchar();

    //maxe在i = n-1 时会访问maxe[n],产生越界问题，故初始化maxe[n] = -INF 或 INT_MIN
    maxe[n] = INT_MIN;
    for(int i = n - 1; i >= 0; i--)
    {
        maxe[i] = max(maxe[i + 1], a[i]);//后缀最大值
    }
    /*
    maxe[4] = max(maxe[5], a[4]) = max(INT_MIN, 4) = 4
    maxe[3] = max(maxe[4], a[3]) = max(4,3) = 4
    maxe[2] = max(maxe[3], a[2]) = max(4,5) = 5
    maxe[1] = max(maxe[2], a[1]) = max(5,1) = 5
    maxe[0] = max(maxe[1], a[0]) = max(5,2) = 5
    maxe = {5,5,5,4,4}
    */

    for(int i = 0; i < n; i++)
    {
        s[top] = a[i];//将当前元素压入栈
        top++;//并将top指向下一个
        while(top && s[top - 1] > maxe[i + 1])
        {
            cout << s[--top] << " ";//弹出并输出栈顶元素
        }
    }
    /*
    a[i] 存放在 s[top -1]，a[i+1]到a[n-1]最大的元素值存放在maxe[i+1],
    如果a[i] > maxe[i+1],说明a[i] 比后面元素都大，则弹出栈并输出

    i = 0; a[i] = a[0] = 2; s = {2};       maxe[i+1] = maxe[1] = 5;       3>5?否，不弹出      -
    i = 1; a[i] = a[1] = 1; s = {2,1};     maxe[i+1] = maxe[2] = 5;       2>5?否，不弹出      -
    i = 2; a[i] = a[2] = 5; s = {2,1,5};   maxe[i+1] = maxe[3] = 4;       5>4?是，弹出        5
    i = 3; a[i] = a[3] = 3; s = {2,1,3};   maxe[i+1] = maxe[4] = 4;       3>4?否，不弹出      -
    i = 4; a[i] = a[4] = 4; s = {2,1,3,4}; maxe[i+1] = maxe[5] = INT_MIN; 4>INT_MIN?是，弹出  4
                            s = {2,1,3};   maxe[i+1] = INT_MIN;           3>INT_MIN?是，弹出  3
                            s = {2,1};     maxe[i+1] = INT_MIN;           1>INT_MIN?是，弹出  1
                            s = {2};       maxe[i+1] = INT_MIN;           2>INT_MIN?是，弹出  2
    */

    //弹出剩余元素（如果栈未空）
    while(top)
    {
        cout << s[--top] << " ";
    }

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