题解 | 火车进站

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static List<List<Integer>> result = new ArrayList<>();
    public static List<Integer> list = new ArrayList<>();
    public static HashSet<Integer> set = new HashSet<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int []trains = new int[n];
            for (int i = 0; i < n; i++) {
                trains[i] = in.nextInt();
            }
            dfs(0, trains);
            List<String> ans = new ArrayList<>();

            for (int i = 0; i < result.size(); i++) {
                List<Integer> list1 = result.get(i);
                //筛选出合法的出栈排列
                if (validateStackSequences(trains, list1)) {
                    StringBuilder st = new StringBuilder();
                    for (int j = 0; j < list1.size(); j++) {
                        
                        st.append(list1.get(j));
                    }
                    //转变成字符串方便字典序排序
                    ans.add(st.toString());
                }
            }
            Collections.sort(ans);
           
            for (int i = 0; i < ans.size(); i++) {
                String s = ans.get(i);
                for (int j = 0; j < s.length(); j++) {
                    int num = s.charAt(j) - '0';
                    if (j == s.length() - 1) {
                        System.out.println(num);

                    } else {
                        System.out.print(num);
                        System.out.print(" ");
                    }

                }


            }
        }
    }
    //得出N个元素的全排列（*******）
    public static void dfs(int i, int[] nums) {
        if (i == nums.length)
            return;

        for (int j = 0; j < nums.length; j++) {
            if (!set.contains(nums[j])) {
                list.add(nums[j]);
                set.add(nums[j]);
                dfs(i + 1, nums);
                if (list.size() == nums.length) {
                    result.add(new ArrayList<>(list));

                }
                list.remove(i);
                set.remove(nums[j]);
            }

        }

    }
    //判断一个排列是否是合法的出栈顺序（*****）
    public static boolean validateStackSequences(int[] pushed,
            List<Integer> popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        int top = 0;

        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && top < popped.size() &&
                    popped.get(top) == stack.peek()) {
                stack.pop();
                top++;
            }

        }


        return stack.isEmpty();

    }
}