题目要求

给定一个由 1 - n 组成的数组和一个栈，并按照数组的顺序入栈。

在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列

解题思路：贪心

要想输出的序列字典序尽可能大，必然用到贪心的思想，即每次出栈的数字尽可能大。具体思路如下：

1、出栈序列的第一个数字必然为n，我们按顺序入栈，直到n入栈时，将n出栈。

2、接下来我们要从尚未入栈的数字中找到其最大值maxi。循环比较maxi和栈顶元素的大小，如果栈顶元素更大，那么该元素出栈，直到栈顶元素小于maxi为止。

3、继续按顺序入栈，直到maxi入栈时，将maxi出栈。

4、重复步骤2和3，直到数组中所有数字都入栈为止。最后将栈中所有元素出栈，得到最终序列。

这个思路的难点在于如何获得每一个maxi。

动态规划

我们创建一个dp数组，让dp[i]表示数组中第i个元素开始到数组末尾之间的最大元素。

那么有动态转移方程 dp[i] = max(a[i], dp[i + 1])。

初始化时，dp[n - 1] = a[n - 1]，然后让i从后到前遍历即可。

很显然，dp[i]就是每个位置i对应的maxi。

c++的set容器

set容器是一个有序的容器，其底层是红黑树，增删改查的时间复杂度都是O(logN)。

这一题我们可以用set容器来代替dp数组。

初始时将1 - n全部插入到set中，每当有元素入栈，则将该元素从set中删除。而每次获取的maxi，即为set中剩余元素的最大值，可以直接用迭代器rbegin得到。

c++代码

下面为使用set容器的代码。你可以尝试自己实现dp数组。

注意要防止越界，当set中容量为0时，可以将maxi设置为-1。

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