题解 | #栈和排序#

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>s;//定义一个栈用来存储数据
        int n = aLen;
        vector<int>res;//用来返回结果
        vector<bool> vis(aLen + 1,0);//用来标记哪个数字出现过
        for(int i = 0;i < aLen;i ++){//遍历数组
            s.push(a[i]);//压入栈
            vis[a[i]] = 1;//压入一个数就把对应的数字标记为1
            
            while(n && vis[n]) n--;// //检测现有栈中有多少个数出现了就是较大的哪些数出现了（从大到小）
            
            while(!s.empty() && n <= s.top()){
                //然后将栈中>=n的元素出栈
                res.push_back(s.top());
                s.pop();
            }
        }
        
        //如果栈没为空就按照栈中原样直接出栈
        while(!s.empty()){
            int temp = s.top();
            res.push_back(temp);
            s.pop();
        }
        return res;
    }
};