题解 | 栈和排序

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] P = new int[n];
        for (int i = 0; i < n; i++) {
            P[i] = scanner.nextInt();
        }
        int[] suffixMax = new int[n + 1];
        suffixMax[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            suffixMax[i] = Math.max(P[i], suffixMax[i + 1]);
        }
        Deque<Integer> stack = new ArrayDeque<>();
        List<Integer> output = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            stack.push(P[i]);
            while (!stack.isEmpty() && stack.peek() >= suffixMax[i + 1]) {
                output.add(stack.pop());
            }
        }
        while (!stack.isEmpty()) {
            output.add(stack.pop());
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < output.size(); i++) {
            sb.append(output.get(i));
            if (i < output.size() - 1) {
                sb.append(" ");
            }
        }
        System.out.println(sb);
    }
}