题解 | #栈和排序#

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(vector<int> &nums) {
        // write code here
        unordered_set<int> set;
        stack<int> st;
        vector<int> ans;
        int n = nums.size();
        ans.reserve(n);
        int index = n;

        for (const auto &a : nums) {
            st.push(a);
            if ((set.count(index) == false) && a != index) {
                set.insert(a);
                continue;
            }

            while (!st.empty() && st.top() == index) {
                ans.emplace_back(st.top());
                set.erase(st.top());
                st.pop();
                while (set.count(--index) == true && st.top() != index);
            }
        }
        while (!st.empty()) {
            ans.emplace_back(st.top());
            st.pop();
        }

        return ans;
    }
};