题解 | #火车进站#
火车进站
https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static LinkedList<Integer> deque = new LinkedList();
static ArrayList<String> list = new ArrayList();
static int[] arr;
static int N;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNextInt()) {
N = scan.nextInt();
arr = new int[N];
for(int i =0;i<arr.length;i++) {
arr[i]=scan.nextInt();
}
f (0, 0, "");
Collections.sort(list);
for(String s:list) {
System.out.println(s);
}
deque.clear();
list.clear();
}
}
/**
*
* @param i 当前要进站的车序号
* @param s_out 累计出站的车数
* @param path 出站顺序记录
*/
public static void f(int i, int s_out, String path) {
//前面的不用出，新来的直接进站
if(i<N) {
//新来的进站
deque.push(arr[i]);
// 通知再下一辆进站
f(i+1, s_out, path);// i+1 不能超过N，数组下标不能越界
deque.pop();// 回复原样，走下面的逻辑
}
//先等前面的出栈，这个再进站
if(!deque.isEmpty()) {
int x = deque.pop();
if(s_out+1 ==N) {// 所有车子都出站了
list.add(path+x);
deque.push(x); //复原返回上层调用
return;
}
f(i, s_out+1, path+x+" ");
deque.push(x);//复原返回上层调用
}
}
}
