HJ113 火车进站

题目描述

火车站一共有 n 辆火车需要入站，每辆火车有一个编号，编号为 1 到 n。同时，也有火车需要出站，由于火车站进出共享一个轨道，所以后入站的火车需要先出站。换句话说，对于某一辆火车，只有在它之后入站的火车都出站了，它才能出站。

现在，已经知道了火车的入站顺序，你需要计算，一共有多少种不同的出站顺序。按照字典序从小到大依次输出全部的出站顺序。

解题思路

这道题本质上是求栈的出栈序列。栈的特点是后进先出(LIFO)，因此： - 每次决策有两个选择：入栈 或 出栈 - 只有栈不为空时才能出栈 - 所有火车都入完且栈空时得到一个完整序列

使用深度优先搜索(DFS)遍历所有可能的出站顺序。

代码实现

res = []

def dfs(wait, stack, out):
    if not wait and not stack:
        res.append(' '.join(map(str, out)))
    if wait:
        dfs(wait[1:], stack + [wait[0]], out)
    if stack:
        dfs(wait, stack[:-1], out + [stack[-1]])

n, nums = int(input()), list(map(int, input().split()))
dfs(nums, [], [])
for i in sorted(res):
	print(i)

代码解析

核心函数 dfs(wait, stack, out)

参数	含义
wait	等待入站的火车队列
stack	当前停在站内尚未出站的火车（栈）
out	已经完成出站的序列

递归逻辑

1. 终止条件：当等待队列为空且栈为空时，说明所有火车都已出站，记录当前序列
2. 入栈分支：如果有火车等待入站，可以选择让它入栈
3. 出栈分支：如果栈不为空，可以选择让栈顶火车出站

搜索树示意（以 1 2 3 为例）

初始: wait=[1,2,3], stack=[], out=[]

                        []
                       /
                     入1
            wait=[2,3], stack=[1], out=[]
           /                         \
        入2                          出1
  wait=[3], stack=[1,2], out=[]   wait=[2,3], stack=[], out=[1]
   /        \                         |
入3        出2                      入2
wait=[],   wait=[3],stack=[1],      wait=[3],stack=[2],out=[1]
stack=[1,2,3]    out=[2]                 |
   |             ...                 入3
出3                                wait=[],stack=[2,3],out=[1]
   |                                  |
出2                                 出3
   |                                  |
出1                                 出2
   |                                  |
[3,2,1]                            出1
                                   [1,3,2]

关键点：根节点栈为空，无法出栈。只有入了1之后，才能从 stack=[1] 状态选择”出1”。

复杂度分析

• 时间复杂度：O(2^n) - 每个火车最多入栈、出栈各一次
• 空间复杂度：O(n) - 递归栈深度

优化建议

当前实现已经是比较简洁的写法。如果需要进一步优化，可以考虑：

1. 使用 itertools：C++ 可用 next_permutation，Python 可用 itertools
2. 剪枝：当等待队列和栈都为空时直接返回
3. 字典序优化：搜索顺序自然保证字典序输出

对于 n ≤ 10 的范围，当前实现完全足够。