题解 | #栈和排序#

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int n) {
        // write code here
        stack<int> stk;
        vector<int> res;
        vector<int> vis(n + 1, false); //将已入栈的较大元素标记
        int now = n; //当前应当出栈对元素，n一定是第一个出栈的元素
        for(int i = 0; i < n; i ++){
            stk.push(a[i]);
            vis[a[i]] = true;
            while(now > 0 && vis[now]) now --; //应当出栈的为>=n的元素
            while(!stk.empty() && stk.top() >= now){
                res.push_back(stk.top()); stk.pop();
            }
        }
        while(!stk.empty()){
            res.push_back(stk.top()); stk.pop();
        }
        return res;
    }
};