题解 | 栈和排序

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型vector 描述入栈顺序
     * @return int整型vector
     */
    vector<int> solve(vector<int>& a) {
        int size = a.size();
        vector<int> ans, pre(size);
        
        stack<int> stk;
        pre[size-1] = INT_MIN;   
        for(int i=size-2; i>=0; i--){  //得到每一个数对应的后面的最大值,在进行入栈操作时,若本数大于辅助数组对应的数即后面出现的最大的数，则进入答案数组。若不大于，入栈，栈中一直是当前非数组中非最大的数；保证了进入的是当前剩余的最大的数；
            pre[i] = max(pre[i+1], a[i+1]);
        }
        
        for(int i=0; i<size; i++){
            if(a[i] > pre[i]){  //本数是当前剩余的最大数
                ans.push_back(a[i]);
                int lastMax = pre[i];

                while(!stk.empty() && stk.top() > lastMax){  //反过来处理栈, 因为最大数改变了，栈中的元素可能变成当前最大数；
                    ans.push_back(stk.top());
                    stk.pop();
                }
            }else{
                stk.push(a[i]);
            }
        }

        while(!stk.empty()){  //最后处理剩余，栈里是递增排序的；
            ans.push_back(stk.top());
            stk.pop();
        }

        return ans;
    }
};