题解 | 栈和排序

要输出出栈序列的最大字典排序：

1. 栈顶的元素 大于 所有的未入栈元素的最大值：输出栈顶到情况2

2.栈顶小于为入栈元素的最大值：

push(a[i])。

最后将所有栈中元素输出即可。

值得注意的是，这里求数组中未入栈元素的最大值时间复杂度不能过大，否则会导致不通过.

可以采取max函数从最后一个数开始预处理。

#include <iostream>
#include <stack>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    stack<int> s;
    for(int k=0;k<n;k++){
        cin>>a[k];

    }
    vector<int> b = a;
    int m[n];//对应当为第i个数入栈时，其后面未入栈元素的最大值.
    m[n-1]=a[n-1];
    for(int i=n-2;i>=0;i--){
        m[i] = max(a[i],m[i+1]);
    }

    for(int i=0;i<n;i++){
        if(s.empty()){
            s.push(a[i]);
        }else{
            while(!s.empty() && s.top()>m[i]){
                cout<<s.top()<<" ";
                s.pop(); 
            }
            s.push(a[i]);

        }
    }
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }

}