思路：

题目的主要信息：

入栈顺序为给定的数组的顺序
在不打乱入栈顺序的前提下尽量做到由大到小排序输出入栈的元素
若无法办到，需要按字典序最大输出

无论是由大到小输出还是按字典序最大输出，都是要求大数在前，小数在后。这些元素都是按照数组顺序进栈的，何时出栈取决于它们后面是否还有比它们更大的元素进入，如果有，则它们先进栈，等后续最大元素先输出，若是无，则输出当前元素。

方法一：逆序记录后续最大元素

具体做法：

可以用一个dpmax数组，记录在第i个元素出现以后，第i到第n的最大值，仅需逆序往前比较即可得到dpmax数组。然后遍历给定的顺序数据，如果当前元素a[i]大于dpmax[i]，即是当前元素比后续所有元素都大，则该元素可以直接出栈，否则入栈等待。最后记得要输出栈中残留的元素。

class Solution {
public:
    vector<int> solve(int* a, int aLen) {
        vector<int> dpmax(aLen + 1, 0);  //dpmax表示第i个数出现后，其后到n为止的最大值
        for(int i = aLen - 1; i > 0; i--) 
            dpmax[i] = max(a[i], dpmax[i + 1]);  //逆向遍历才能找到dpmax
        stack<int> s;
        vector<int> res;
        for(int i = 0; i < aLen; i++){  //遍历数组
             while(!s.empty() && s.top() >= dpmax[i]){  //当前栈顶元素大于其后要出现的最大值
                 res.push_back(s.top());                //直接让其出栈
                 s.pop();
             }
             s.push(a[i]);
        }
        while(!s.empty()){  //剩余元素出栈
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，最坏情况全部逆序，栈中存满元素，也相当于两次循环（for一次，for结尾全部出栈一次）。
空间复杂度： $O (n)$ ，辅助数组dpmax与栈

方法二：记忆最大值访问

具体做法：

因为给定的是1-n的数据，所有最大值必定是n，我们可以设置一个dp数组表示这个最大值是否被访问过，如果这个最大值已经被用过出栈了，我们需要递减以更新最大值，如果这个最大值没有被访问过可以直接比较栈顶元素和它的大小，当栈顶较大时，出栈即可。图片说明

class Solution {
public:
    vector<int> solve(int* a, int aLen) {
        stack<int> s;
        int max = aLen;
        vector<bool> dp(aLen + 1, false);  //记录是否访问过
        vector<int> res;
        for(int i = 0; i < aLen; i++){
            s.push(a[i]);
            dp[a[i]] = true;
            while(max > 0 && dp[max] == true)  //当max已经出栈后，需要递减获取下面的max
                max--;
            while(!s.empty() && s.top() >= max){  //当前栈顶比max大或者等，出栈
                res.push_back(s.top());
                s.pop();
            }
        }
        while(!s.empty()){  //剩余元素出栈
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，一次遍历即可
空间复杂度： $O (n)$ ，辅助数组dp与栈

题解 | #栈和排序#

思路：