题解 | 栈和排序

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String[] input = in.nextLine().split(" ");
        int[] inputArray = new int[n];
        for (int i = 0; i < n; i++) {
            inputArray[i] = Integer.parseInt(input[i]);
        }

        // 栈模拟
        Deque<Integer> stack = new ArrayDeque<>();
        StringBuilder output = new StringBuilder();
        int maxValue = n; // 当前还未出栈的最大值
        int index = 0;   // 指向下一个要入栈的元素

        while (index < n || !stack.isEmpty()) {
            // 按inputArray顺序将一个元素入栈
            if (index < n) {
                stack.push(inputArray[index]);
                index++;
            }
            // 将一个元素入栈之后，开始尽可能多地将元素出栈，尽可能多地弹出当前最大值
            // 这里必须用while，因为上一轮循环中可能有元素入栈了，但是在上一轮中没有机会出栈，而该元素在这轮循环中就可能有机会出栈，以此类推。
            while (!stack.isEmpty() && stack.peek() == maxValue) {
                output.append(stack.pop()).append(' ');
                maxValue--;// maxValue--导致了上一轮循环中没有机会出栈的元素变得有机会出栈。
                            //如果一直能出栈，maxValue就一直--，就一直继续能出栈。
            }
            // 如果不能弹出最大值且已全部入栈，只能弹出栈顶
            if (index == n && !stack.isEmpty() && stack.peek() != maxValue) {
                output.append(stack.pop()).append(' ');
            }
        }

        // 输出结果，去除末尾多余空格
        System.out.println(output.toString().trim());
    }
}

字典序：从第一个元素开始，逐位比较两个序列。遇到第一个不同的位置，谁的数字大，谁的字典序就大。

所以靠前的数字具有决定性的作用。前面的某一位数字小了，后面怎么排都是小的。

输入是1到n的排列，那么无论顺序如何，n都是这些数中的最大值。

思路：

1，依次入栈原序列的每一个数字num，每次将num入栈时都判断它是否为当前能出栈的最大值maxValue（maxValue的初始值为n），如果是则立即出栈。

2，该数字出栈后，当前能出栈的最大值就变成了maxValue - -。此时需要继续尝试出栈，看看栈顶元素是否等于maxValue - -，如果是，栈顶元素出栈。依次类推，直到栈顶元素与maxValue - -不相等。

3，如果原序列中全部元素都已经入栈，且无法出栈与maxValue相等的那个元素，则只能弹出当前栈顶的元素（当前栈顶的这个元素必然小于maxValue，但是在栈的限制下只能这么做）。

在过程中只要有机会把更大的数提前放到输出序列前面，就绝不让更小的数先出栈，满足字典序的排序。

这样每一步都做出对字典序最有利的选择，最终得到的就是所有合法出栈序列中字典序最大的。