题解 | 栈和排序

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

// 参考：https://chat.deepseek.com/share/xbfwwa19v00i85knpb
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        // 顺序遍历存入arr
        for(int i = 0;i<N;i++){
            arr[i] = in.nextInt();
        }
        
        // 贪心算法
        // 计算每个位置之后的最大值
        int[] maxAfter = new int[N+1];
        maxAfter[N] = 0;
        // 输入：2 1 5 3 4
        // maxAfter: 5 5 5 4 4 0
        for(int i = N-1;i>=0;i--){
            maxAfter[i] = Math.max(arr[i],maxAfter[i+1]);
        }

        Stack<Integer> st = new Stack<>();
        List<Integer> res = new ArrayList<>();

        // 顺序入栈
        for(int i = 0;i<N;i++){
            st.push(arr[i]);
            // 出栈时机：当栈顶元素大于后续未入栈元素，就出栈（因为这是当前能出的最大数）
            while(!st.isEmpty() && st.peek() >= maxAfter[i+1]){
                res.add(st.pop());
            }
        }

        for(int i = 0;i<res.size();i++){
            System.out.printf("%d",res.get(i));
            if(i != res.size()-1){
                System.out.printf(" ");
            }
        }
    }
}