题解 | #栈和排序#

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(vector<int> a) {
        stack<int>s;//定义一个栈用来存储数据
        int aLen=a.size();
        int n = aLen;
        vector<int>res;//用来返回结果
        //方法二
//        vector<bool> vis(aLen + 1,false);
        vector<int> t(aLen,0);
        int temp=-1;
        for(int i=aLen-1;i>=0;i--){
            temp=max(a[i],temp);
            t[i]=temp;//记录后续进栈的最大值
        }
//        int M=-1;   
        for(int i=0;i<aLen;i++){//将栈中大于后序的数据先行弹出
            while(!s.empty()&&s.top()>t[i]){
                res.push_back(s.top());
                s.pop();
            }
            s.push(a[i]);
//            vis[a[i]]=true;
            if(s.top()==t[i]){
                res.push_back(s.top());
                s.pop();
            }
            
        }
        while(!s.empty()){
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
}; 
        //方法一
        // for(int i=0;i<aLen;i++){
        //     vis[a[i]]=true;
        //     s.push(a[i]);
        //     while(n && vis[n]) n--;
        //     while(!s.empty() && n <= s.top()){
        //         //然后将栈中>=n的元素出栈
        //         res.push_back(s.top());
        //         s.pop();
        //     }
        // }