题解 | #火车进站#

import java.util.*;

public class Main {
    static int n;
    static int[] inArr;
    static ArrayList<String> result;
    static ArrayList<Integer> temp;
    static Stack<Integer> stack;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        inArr = new int[n];
        for (int i = 0; i < n; i++) {
            inArr[i] = in.nextInt();
        }
        temp = new ArrayList<>();
        result = new ArrayList<>();
        stack = new Stack<>();
        stack.push(inArr[0]);
        dfs(1);
        Collections.sort(result);
        for (String s : result) {
            System.out.println(s);
        }
    }

    private static void dfs(int index) {
        if (index == n && stack.empty()) {
            String str = "";
            for (int i = 0; i < temp.size(); i++) {
                str += temp.get(i) + " ";
            }
            result.add(str);
            return;
        }
        if (index < n) {
            stack.push(inArr[index]);
            dfs(index + 1);
            stack.pop();
        }
        if (stack.size() > 0) {
            Integer peek = stack.peek();
            temp.add(peek);
            stack.pop();
            dfs(index);
            stack.push(peek);
            temp.remove(temp.size() - 1);
        }
    }
}

解题思路:

1, 采用了深度搜索的方法, 同时利用了栈的数据结构来处理本题