华为机试—火车进站

题目

火车站一共有 n 辆火车需要入站，每辆火车有一个编号，编号为 1 到 n。
同时，也有火车需要出站，由于火车站进出共享一个轨道，所以后入站的火车需要先出站。换句话说，对于某一辆火车，只有在它之后入站的火车都出站了，它才能出站。
现在，已经知道了火车的入站顺序，你需要计算，一共有多少种不同的出站顺序。按照字典序从小到大依次输出全部的出站顺序。

示例

输入：3

           1 2 3

输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

说明：

在这个样例中，每一种出栈顺序的详细出入站状况为（黑色字体代表入站、粉色字体代表出站）：
∙1→1→2→2→3→3；
∙1→1→2→3→3→2；
∙1→2→2→1→3→3；
∙1→2→2→3→3→1；
∙1→2→3→3→2→1。
输出若干行，每行输出 n 个整数，代表一种出站顺序。你需要按照字典序从小到大依次输出。

分析

这是一个关于栈操作和全排列的问题，我们可以使用深度优先搜索（DFS）算法结合栈来解决。

DFS

算法思路

我们使用一个栈来模拟火车的入站和出站操作。初始时，栈为空，我们从入站序列的第一个火车开始处理。

在每一步，我们有两种选择：

• 将当前入站的火车入栈。
• 如果栈不为空，将栈顶的火车出站。

使用深度优先搜索（DFS）来遍历所有可能的入栈和出栈操作组合。

当入站序列中的所有火车都已入站，并且栈为空时，我们得到了一种合法的出站顺序。将所有合法的出站顺序存储在一个数组中，并按照字典序从小到大输出。

时间复杂度：O()

空间复杂度：O()

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;// 深度优先搜索函数
void dfs(vector<int>& inSeq, stack<int>& st, vector<int>& outSeq, vector<vector<int>>& allOutSeqs) {// 如果入站序列和栈都为空，说明找到了一种合法的出站顺序if (inSeq.empty() && st.empty()) {allOutSeqs.push_back(outSeq);return;}// 如果入站序列不为空，将当前火车入栈if (!inSeq.empty()) {int temp = inSeq.front();inSeq.erase(inSeq.begin());st.push(temp);dfs(inSeq, st, outSeq, allOutSeqs);inSeq.insert(inSeq.begin(), temp);st.pop();}// 如果栈不为空，将栈顶火车出站if (!st.empty()) {int temp = st.top();st.pop();outSeq.push_back(temp);dfs(inSeq, st, outSeq, allOutSeqs);outSeq.pop_back();st.push(temp);}
}int main() {int n;cin >> n;vector<int> inSeq(n);for (int i = 0; i < n; ++i) {cin >> inSeq[i];}stack<int> st;vector<int> outSeq;vector<vector<int>> allOutSeqs;dfs(inSeq, st, outSeq, allOutSeqs);// 按照字典序排序sort(allOutSeqs.begin(), allOutSeqs.end());// 输出所有出站顺序for (const auto& seq : allOutSeqs) {for (int num : seq) {cout << num << " ";}cout << endl;}return 0;
}