一、题目描述

题目大意：给你一个1到n的排列和一个栈，入栈顺序给定，你要在不打乱入栈顺序的情况下，对数组进行从大到小排序，当无法完全排序时，请输入字典序最大的出栈序列
注意审题：数据范围 1 <= n <= 1000000

二、算法1（贪心）

解题思路

1. 要使得出栈序列字典序最大，首先想到的就是令高位尽可能地大，由于栈中数据不会重复因此，我们出栈的时机就是当前入栈元素若是大于之后将要要入栈的元素，那么就将其出栈，这样保证了出栈序列的高位尽可能的大，且当前元素出栈后，还要考虑栈顶元素与之后将要入栈元素之间的大小关系，若栈顶元素大于之后将要入栈的元素，那么就将其出栈，重复判断直到栈空或条件不满足为止
2. 考虑到题目所给出的数据范围比较大，暴力检查的方式不可取，我们可以想一下如何优化判断的时间复杂度
3. 要动态的查找当前数与之后将要入栈的元素之间的大小关系，我们很容易想到平衡树，它支持的查找和的删除操作，使用C++的set容器。我们可以先将全部元素全部插入集合，然后依次遍历，每次检查当前数与之后待入栈元素的大小关系，缺点之后再确定与当前栈顶元素的关系，这样我们可以保证每个元素只会插入集合一次，删除一次，出入栈一次，时间复杂度为，但是很可惜，还是超时了

代码实现（C++11）

class Solution {
public:
    vector<int> solve(int* a, int aLen) {
        vector<int> ans;
        set<int> right;    // 右集合
        for (int i = 0; i < aLen; i++) {    // 先将全部元素都插入集合
            right.insert(a[i]);
        }
        stack<int> stk;
        for (int i = 0; i < aLen; i++) {
            // 只要a[i]后面都没有比它大的数, 就出栈
            if (right.size()) {    // 集合不为空
                auto it = right.end();
                --it;    // 找到最大值
                if (*it == a[i]) ans.push_back(a[i]);    // 后面没有比a[i]大的数, 加入出栈序列
                else stk.push(a[i]);    // 后面后比a[i]大的数, a[i]入栈
                it = right.find(a[i]);
                right.erase(it);    // 从集合中删除a[i]
                while (!stk.empty() && !right.empty()) {    // 不断检查栈顶
                    auto it = right.end();
                    --it;
                    if (*it < stk.top()) {
                        ans.push_back(stk.top());
                        stk.pop();
                    }
                    else break;
                }
            }
            else ans.push_back(a[i]);    // 集合为空，直接加入出栈序列
        }

        // 若栈非空, 则依次出栈并加入到出栈序列中
        while (stk.size()) {
            ans.push_back(stk.top());
            stk.pop();
        }

        return ans;
    }
};

时间复杂度：，n为数组长度，每个元素只会插入集合一次，删除一次，出入栈一次，时间复杂度为
空间复杂度：，使用了一个栈和一个集合，空间复杂度为

三、算法2（预处理最大值）

解题思路

1. 上个算法的瓶颈在于动态检查耗时仍然过多，必须想到的方式进行判断操作
2. 我们可以预处理一个数组f，f[i]表示i之后的最大元素，这样我们就能以的时间复杂度进行检查操作，总时间复杂度优化到了级别

代码实现（C++11）

class Solution {
public:
    vector<int> solve(int* a, int aLen) {
        vector<int> ans, f(aLen);
        stack<int> stk;
        // 倒序预处理最大值
        f[aLen - 1] = INT_MIN;
        for (int i = aLen - 2; i >= 0; i--) {
            f[i] = max(a[i + 1], f[i + 1]);
        }

        for (int i = 0; i < aLen; i++) {
            if (a[i] > f[i]) {    // 若当前元素大于之后将要入栈的元素
                ans.push_back(a[i]);
                int lastMax = f[i];    // 之后将要入栈的元素的最大值

                // 检查栈顶元素是否大于之后将要入栈的元素的最大值
                while (!stk.empty() && stk.top() > lastMax) {
                    ans.push_back(stk.top());
                    stk.pop();
                }
            }
            else stk.push(a[i]);    // 直接入栈
        }

        // 若栈非空, 则依次出栈并加入到出栈序列中
        while (!stk.empty()) {
            ans.push_back(stk.top());
            stk.pop();
        }

        return ans;
    }
};

时间复杂度：，n为数组长度，进行两次遍历，时间复杂度为
空间复杂度：, 辅助栈空间和辅助数组空间占用为