(牛客)前端Ai面试：栈和排序

示例

输入：
[2,1,5,3,4]
返回值：
[5,4,3,1,2]

输入：
[1,2,3,4,5]
返回值：
[5,4,3,2,1]

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 栈排序
     * @param a int整型vector 描述入栈顺序
     * @return int整型vector
     */
    stack<int> st;
    vector<int> ans;
    vector<int> solve(vector<int>& a) {
        // write code here
        int max=a.size();
        vector<int> f(max+1,0);
        for(int i=0;i<a.size();i++)
        {
            st.push(a[i]);
            f[a[i]]=1;//标记为已经加入了栈中
            while(max&&f[max]) 
            {
                max--;//去查找未加入栈中的最大值
            }
            while(st.size()&&st.top()>=max)//如果栈顶值会大于等于当前最大值
            {
                ans.push_back(st.top());//直接抛出答案
                st.pop();
            }
        }
        return ans;
    }
};