NC115 栈和排序

class Solution {
public:
    vector<int> solve(vector<int>&a) { 
        //ans用来存最后的答案，f数组用来存后面要入栈的剩余元素中的最大值
        //倒序处理最大值
        vector<int> ans,f(a.size());
        stack<int> stack1;
        //先让f数组的最后一个元素的值为无穷小
        //再从f数组倒数第二位开始填写
        //倒序将f数组和a数组从最后一位开始进行逐位比较，选出两者中的最大值放在f的前一位
        //这样f[i]数组记录的就是a数组的后i+1位的最大值
        f[a.size()-1]=INT_MIN;
        for(int i=a.size()-2;i>=0;i--){
            f[i]=max(f[i+1],a[i+1]);
        }
        for(int i=0;i<=a.size()-1;i++){
            //如果即将入栈的元素比后面还没入栈的元素中的最大值还要大，就说明这个元素是最大的
            //就记在ans中，并更新lastmax(用来记录后面还没入站的元素中的最大值)
            //再将栈内的元素与lastmax进行比较，如果比它大，就出栈，记在ans里
            if(a[i]>f[i]){
                ans.push_back(a[i]);
                int lastmax=f[i];
                while(!stack1.empty()&&stack1.top()>lastmax){
                    ans.push_back(stack1.top());
                    stack1.pop();
                }
            }else{
         //如果即将入栈的a数组的这个元素比后面剩余要入栈的元素中的最大值要小，就将该元素入栈
                stack1.push(a[i]);
            }
        }
        //最后如果栈非空，就按顺序出栈，记在答案ans中 
        while(!stack1.empty()){
            ans.push_back(stack1.top());
                stack1.pop();
        
        }
        return ans;
    }
};