题解 | #栈和排序#

题目描述
给你一个1->n的排列和一个栈，入栈顺序给定
你要在不打乱入栈顺序的情况下，对数组进行从大到小排序
当无法完全排序时，请输出字典序最大的出栈序列

方法一：暴力求解--逆序记录后续最大元素

求解思路
对于本题目，无论是由大到小输出还是按字典序最大输出，都是要求大数在前，小数在后。因此元素何时出栈取决于它们后面是否还有比他们更大的元素进入，如果有，则它们先进栈，等后续最大元素先输出，若无，则输出当前元素。因此我们可以用一个dpmax的数组，记录第i个元素出现以后，第i到第n的最大值，仅需逆序往前比较即可。然后根据遍历的结果对元素能否入栈做出判断。

图片说明

解题代码

class Solution {
public:
    vector<int> solve(int* hy, int hyLen)
    {
        vector<int> dpmax(hyLen + 1, 0); // dpmax存储最大值
        for(int i = hyLen - 1; i > 0; i--) 
            dpmax[i] = max(hy[i], dpmax[i + 1]); // 反向遍历找dpmax
        stack<int> s; // 声明栈
        vector<int> myres; // 存储结果
        for(int i = 0; i < hyLen; i++)
        {   //遍历数组
             while(!s.empty() && s.top() >= dpmax[i])
             {   //当前栈顶元素大于其后要出现的最大值
                 myres.push_back(s.top()); // 直接让其出栈
                 s.pop();
             }
             s.push(hy[i]);
        }
        while(!s.empty())
        {  //剩余元素出栈
            myres.push_back(s.top());
            s.pop();
        }
        return myres;//返回排序结果
    }
};

复杂度分析
时间复杂度：队列全部逆序遍历，并且栈中存满元素，时间复杂度为 $O(N)$
空间复杂度：申请的dpmax需要引入额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：优化解法--最大值记忆法

求解思路
对于本题，因为给定的是从1到n的数据，因此我们可以设置一个dp数组表示从n递减到1的时候的当前最大值是否被访问过。如果这个最大值已经被用过出栈了，我们需要递减以更新最大值，如果这个最大值没有被访问过，则可以直接比较栈顶元素和它的大小，当栈顶元素大时，出栈。

图片说明

解题代码

class Solution {
public:
    vector<int> solve(int* hy, int hyLen) {
        stack<int> s; // 声明栈
        int max = hyLen;
        vector<bool> dp(hyLen + 1, false); // 存储最大值
        vector<int> myres; // 存储结果
        for(int i = 0; i < hyLen; i++)
        {
            s.push(hy[i]);
            dp[hy[i]] = true;
            while(max > 0 && dp[max] == true) // max出栈
                max--;
            while(!s.empty() && s.top() >= max)
            {   //当栈顶比max大则出栈
                myres.push_back(s.top());
                s.pop();
            }
        }
        while(!s.empty())
        {   //剩余元素出栈
            myres.push_back(s.top());
            s.pop();
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：申请的dp数组需要引入额外的内存地址空间，因此空间复杂度为 $O(N)$