题解 | #栈和排序#

题解：由于数字在1-n之间，对数组遍历，对已访问的数组将vis[i]置true，没访问的vis[i]为false。
统计a[i]后面的最大值，vis从n=aLen开始统计，第一个为false的就是a[i]后面的最大值。
如果数组后面的最大值比栈顶元素小，就弹出栈顶元素直到不符合条件
当遍历完栈非空就按序弹出栈所有元素，得到最终结果。

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // write code here

        stack<int>st;
        vector<int>res;
        vector<bool>vis(aLen+1,0);
        int n=aLen,i=0;
        while(i<aLen)
        {
            vis[a[i]]=1;
            st.push(a[i]);
            while(n && vis[n])n--;//寻找数组后面的最大值
            while(!st.empty() && n<st.top())//如果数组后面的最大值比栈顶小，弹出栈顶
            {
                res.push_back(st.top());
                st.pop();
            }
            i++;
        }
        while(!st.empty()){res.push_back(st.top());st.pop();}
        return res;
    }
};