题目的主要信息：

给定n列火车的入栈序列， $0 < n < 10$ ，用数列1-9表示每列火车
火车只能从一个方向进，另一个方向出，只有站内的火车出去了，另外的才能进去
要求输出所有火车出站的方案，以字典序排序输出

方法一：全排列+栈

具体做法：

我们可以使用next_permutation函数对于输入的数字序列进行全排列，记录下所有的情况，全排列之前先排序，可以使全排列的结果呈现字典序排序。

然后依次验证每个情况是否符合火车进站出现的次序。根据验证的时候，根据输入的序列依次进栈，如果栈顶元素和要验证的出站顺序刚好一样，不断弹出栈中元素即可。最后如果刚好栈为空，说明这种顺序可以出站，可以输出，否则不能输出。

alt

#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;

bool check(vector<int>& order, vector<int>& out){ //根据进来的顺序检查有无这种出去的顺序
    stack<int> s;
    int j = 0; //out数组的下标
    for(int i = 0; i < order.size(); i++){
        s.push(order[i]); //每次火车入栈
        while(!s.empty() && s.top() == out[j]){ //如果刚好栈顶等于输出，就全部出栈
            s.pop();
            j++;
        }
    }
    return s.empty();
}

int main(){
    int n;
    while(cin >> n){
        vector<vector<int> > output;
        vector<int> nums(n); //记录所有的数字
        vector<int> order(n); //记录数字进来的顺序
        for(int i = 0; i < n; i++){
            cin >> nums[i];
            order[i] = nums[i];
        }
        sort(nums.begin(), nums.end()); //对数字按照字典序排序
        do{
            output.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end())); //获取全排列
        for(int i = 0; i < output.size(); i++){ 
            if(check(order, output[i])){ //检查每一种排列输出的可能性
                for(int j = 0; j < n; j++)
                    cout << output[i][j] << " ";
                cout << endl;
            }
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n * n!)$ ，全排列的复杂度为 $O (n!)$ ，每次验证的时间是 $O (n)$
空间复杂度： $O (n * n!)$ ，记录全排列后的二维数组有 $n!$ 行，每行 $n$ 个元素

方法二：dfs+回溯

具体做法：

我们也可以用dfs来构建全排列，直接输出可能的结果。

对于dfs每次递归，就只有两个操作：要么从栈出弹出一个输出（火车出站），要么从数组中拿出一个加入栈中（火车进战），每次操作完都需要回溯才能够实现检查全排列，如果某一种输出长度到了 $n$ 说明这种序列结束了，可以输出，我们将其加入set中，自动去重排序。

#include<iostream>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;

void dfs(vector<int>& nums, stack<int> s, vector<int> temp, set<vector<int>>& output, int index, int& n){
    if(temp.size() == n){ //该情况结果已经完成
        output.insert(temp);
        return;
    }
    for(int i = 0; i < 2; i++){ //每次两个操作
        if(i == 0 && !s.empty()){ //要么从栈出弹出一个输出
            int num = s.top();
            s.pop();
            temp.push_back(num);
            dfs(nums, s, temp, output, index, n); //继续递归
            s.push(num); //回溯
            temp.pop_back(); 
        }else if(i == 1 && index < n){ //要么从数组中拿出一个加入栈中
            int num = nums[index];
            s.push(num);
            index++;
            dfs(nums, s, temp, output, index, n); //继续递归
            index--; //回溯
            s.pop();
        }
    }
}

int main(){
    int n;
    while(cin >> n){
        vector<int> nums(n);
        for(int i = 0; i < n; i++)
            cin >> nums[i];
        set<vector<int> > output;
        stack<int> s;
        vector<int> temp; //记录某一种情况的输出结果
        s.push(nums[0]); // 默认第一辆车都要先进去
        dfs(nums, s, temp, output, 1, n); //dfs找到全排列
        for(auto iter = output.begin(); iter != output.end(); iter++){ //遍历集合
            for(int i = 0; i < n; i++) //输出集合中每一个数组
                cout << (*iter)[i] << " ";
            cout << endl;
        }
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n! l o g_{2} (n!))$ ，dfs遍历整个全排列，最坏情况下全排列都要输出，那set的排序就是 $O (n! l o g_{2} (n!))$
空间复杂度： $O (n * n!)$ ，set集合最大有 $n!$ 个输出，每个有 $n$ 个元素

题解 | #火车进站#

题目的主要信息：

方法一：全排列+栈

方法二：dfs+回溯