题解 | 栈和排序

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        int[] maxSuffix = new int[n];
        maxSuffix[n - 1] = arr[n - 1];
        for(int i = n - 2; i >= 0; i--) {
            maxSuffix[i] = Math.max(arr[i], maxSuffix[i + 1]);
        }

        Deque<Integer> stack = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            stack.push(arr[i]);
            // 尽可能将当前最大值出栈
            while(!stack.isEmpty() && stack.peek() == maxSuffix[i]) {
                result.add(stack.pop());
            }
        }

        // 剩下的出栈
        while(!stack.isEmpty()) {
            result.add(stack.pop());
        }

        // 输出结果
        for(int i = 0; i < result.size(); i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(result.get(i));
        }
    }
}