题解 | 栈和排序

//算法练习No.20
//贪心算法，输出时尽可能大
//模拟进出栈，后缀最大值
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if(!(cin >> n)) return 0;

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

    //后缀最大值
    vector<int> max_s(n+1,0);//设置哨兵，防止越界
    for(int i = n-1;i>=0;i--)
    {
        max_s[i] = max(max_s[i+1],a[i]);
    }

    stack<int> st;
    bool first = true;// 用于控制空格输出格式

    for(int i=0;i<n;i++)
    {
        st.push(a[i]);
        while(!st.empty() && st.top() > max_s[i+1])//贪心，和后缀数组中最大值相比，找最大
        {
            if(!first) cout << " ";
            cout << st.top();
            st.pop();
            first = false;
        }
    }
    cout << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")