题意整理

• 给定一个1到n的排列和一个栈，并按照排列顺序入栈。
• 在不打乱入栈顺序的情况下，仅利用入栈和出栈两种操作，输出字典序最大的出栈序列。

方法一（动态规划）

1.解题思路

• 首先新建一个栈，用于存放按顺序入栈的元素。
• 再新建一个$dpdp$数组，$dp[i]dp[i]$表示当前元素以及后面出现元素中的最大值。逆向遍历原序列，给$dpdp$数组赋值。
• 然后正向遍历$dpdp$数组，将当前元素入栈，只要栈顶元素比后面所有元素都大，则直接出栈，保证大的值尽量在序列前面。
• 最后还在栈中的元素，按先进后出的顺序赋给结果数组。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        //记录排列的最后一位
        int n=a.length;
        //结果数组
        int[] res=new int[n];
        //新建一个栈
        LinkedList<Integer> stack=new LinkedList<>();
        int id=0;
        //dp[i]表示当前元素以及后面出现元素中的最大值
        int[] dp=new int[n];
        dp[n-1]=a[n-1];
        for(int i=n-2;i>=0;i--){
            dp[i]=Math.max(a[i],dp[i+1]);
        }
        for(int i=0;i<n;i++){
            //将当前元素入栈
            stack.push(a[i]);
            //只要栈顶元素比后面所有元素都大，则直接出栈
            while(!stack.isEmpty()&&i<n-1&&stack.peek()>dp[i+1]){
                res[id++]=stack.pop();
            }
        }
        //最后还在栈中的元素，按先进后出的顺序赋给结果数组
        while(!stack.isEmpty()){
            res[id++]=stack.pop();
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：确定$dpdp$数组需要遍历整个序列，同时后续每个值只会入栈和出栈一次，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外大小为n的栈和$dpdp$数组，所以空间复杂度为$O(n)O(n)$。

方法二（标记数组）

1.解题思路

思路和方法一差不多，都是尽量找出当前在序列中的最大值，让它在序列前面出现。方法一利用$dpdp$数组来确定这样的最大值，方法二则利用标记数组的方式。记录所有已经出现在栈中的元素，并加一个判断，如果当前序列最大值出现在栈中，则减1，后续进行判断，如果当前栈顶元素大于标记的序列最大值，说明当前栈顶元素是最大值，直接出栈。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 栈排序
     * @param a int整型一维数组 描述入栈顺序
     * @return int整型一维数组
     */
    public int[] solve (int[] a) {
        //记录排列的最后一位
        int n=a.length;
        //结果数组
        int[] res=new int[n];
        //新建一个栈
        LinkedList<Integer> stack=new LinkedList<>();
        int id=0;
        //标记数组，判断是否已入栈
        boolean[] f=new boolean[n+1];
        for(int cur:a){
            //只要当前排列最大值在栈中，则将当前排列最大值减1
            while(f[n]){
                n--;
            }
            //只要发现排列的当前最大值在栈中，则弹出栈顶元素
            while(!stack.isEmpty()&&stack.peek()>n){
                res[id++]=stack.pop();
            }
            //将当前元素入栈，并标记出来
            stack.push(cur);
            f[cur]=true;
        }
        //最后还在栈中的元素，按先进后出的顺序赋给结果数组
        while(!stack.isEmpty()){
            res[id++]=stack.pop();
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：序列中的每个值只会入栈和出栈一次，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外大小为n的栈和大小为$n+1n+1$的标记数组，所以空间复杂度为$O(n)O(n)$。