给你一个 1 到 n 的排列和一个栈,并按照排列顺序入栈
你要在不打乱入栈顺序的情况下,仅利用入栈和出栈两种操作,输出字典序最大的出栈序列
排列:指 1 到 n 每个数字出现且仅出现一次
数据范围: NC115 栈和排序 - 图1,排列中的值都满足NC115 栈和排序 - 图2
进阶:空间复杂度NC115 栈和排序 - 图3,时间复杂度NC115 栈和排序 - 图4

示例

  1. 输入:[2,1,5,3,4]
  2. 返回值:[5,4,3,1,2]
  3. 说明:
  4. 操作 结果
  5. 2 入栈;[2] []
  6. 1 入栈;[2\1] []
  7. 5 入栈;[2\1\5] []
  8. 5 出栈;[2\1] [5]
  9. 3 入栈;[2\1\3] [5]
  10. 4 入栈;[2\1\3\4] [5]
  11. 4 出栈;[2\1\3] [5,4]
  12. 3 出栈;[2\1] [5,4,3]
  13. 1 出栈;[2] [5,4,3,1]
  14. 2 出栈;[] [5,4,3,1,2]

思路:如果当前要入栈的元素和之后的元素都没有栈顶元素大,则应出栈。

class Solution {
public:
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @param aLen int a数组长度
     * @return int整型vector
     */
    vector<int> solve(int* a, int aLen) {
        // 目的:元素入栈之后如果后面的数没有比栈顶大的元素,则栈顶出栈

        // 1、先动态规划计算每个数及其后面最大的数
        // 定义数组dp,dp[i]表示第i个元素及其之后最大的元素值
        // 显然,dp数组是要从后往前填充的
        //     dp[n-1] = a[n-1]
        //     dp[i] = max(a[i], dp[i+1])
        vector<int> dp(aLen, 0);
        dp[aLen-1] = a[aLen-1];
        for(int i=aLen-2; i>=0; --i){
            dp[i] = max(a[i], dp[i+1]);
        }

        // 2、元素入栈时先判断栈顶元素和之后要遇到的最大值,
        // 如果小于,新元素入栈
        // 如果大于,栈顶弹出,继续判断栈顶
        vector<int> result;
        stack<int> tmpStack;
        for(int i=0; i<aLen; i++){
            while(!tmpStack.empty() && tmpStack.top()>dp[i]){
                result.push_back(tmpStack.top());
                tmpStack.pop();
            }
            tmpStack.push(a[i]);
        }
        while(!tmpStack.empty()){
            result.push_back(tmpStack.top());
            tmpStack.pop();
        }

        return result;
    }
};