思路:

题目的主要信息:

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

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

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

具体做法:

可以用一个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)O(n)O(n),最坏情况全部逆序,栈中存满元素,也相当于两次循环(for一次,for结尾全部出栈一次)。
  • 空间复杂度:O(n)O(n)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)O(n),一次遍历即可
  • 空间复杂度:O(n)O(n)O(n),辅助数组dp与栈