【错题集-编程题】栈和排序（栈 + 贪心）

牛客对于题目连接：栈和排序_牛客题霸_牛客网 (nowcoder.com)

一、分析题目

每次尽可能的先让当前需要的最大值弹出去。

二、代码

// 修改后的代码
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型vector 描述入栈顺序
     * @return int整型vector
     */
    vector<int> solve(vector<int>& a) {
        int n=a.size();
        vector<int> ret;
        stack<int> st;
        int maxi = n;
        int hash[50010]={0};
        for(int i=0; i<n; i++)
        {
            int x=a[i];
            st.push(x);
            hash[x]=1;
            while(hash[maxi])
                maxi--;
            while(st.size() && st.top()>=maxi)
            {
                ret.push_back(st.top());
                st.pop();
            }
        }
        return ret;
    }
};

三、反思与改进

没有处理好 maxi 的变化，导致下一个数不是比 maxi 小时，输出结果不符合题意。