题目的主要信息：

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。要求输出所有火车出站的方案，以字典序排序输出。

方法一：

采用递归。judge函数用于判断当前出站顺序是否正确，每次将入栈序号存入stk栈中，如果当前stk栈顶元素和出站顺序相同，则可以出站，最后如果stk为空，表示这个出站顺序是正确的。

dfs中用一个访问数组记录当前序号是否被访问过，如果当前元素在此次排列中还没被访问过，则访问当前元素，继续递归；如果当前元素被访问过，则遍历下一个元素。递归可以遍历所有可能的排列，最后判断每种排列的可行性。 alt 具体做法：

#include<iostream>
#include<stack>

using namespace std;

bool visit[15]={0};
int stackOut[15],step=0,n,stackIn[15];

bool judge(){//判断当前出站顺序是否正确
    stack<int> stk; 
    for(int in=1,out=1;in<=n;in++){
        stk.push(stackIn[in]);
        while(out<=n&&!stk.empty()&&stk.top()==stackOut[out]){//如果当前栈顶元素和出站顺序相同，则可以出站
            stk.pop();
            out++;
        }
    }
    return stk.empty();
} 
void dfs(int step){
    for(int i=1;i<=n;i++){
        if(visit[i]==0){//当前火车还没被访问
            visit[i]=1;
            stackOut[step]=i;//第step个出站的为第i列火车
            if(step==n){//如果已经排好n个出站顺序了
                if(judge()){//判断当前顺序是否有效
                    for(int j=1;j<=n;j++){
                        cout<<stackOut[j]<<" ";
                    }
                    cout<<endl;
                } 
            }else{//还没有排好所有出站顺序，继续递归
                dfs(step+1);
            }
            visit[i]=0;//回溯
        }
    }
}
int main(){
    while(cin>>n){    
        for(int i=1;i<=n;i++){
            cin>>stackIn[i];
        }
        dfs(1);
    }
    return 0;
}

复杂度分析：

时间复杂度：O(n*n!)，dfs会遍历所有排列情况，每一种排列都需要花 $O (n)$ 时间去判断是否正确。
空间复杂度：O(n∗n!)，最坏情况下，全排列n!全部正确，每次有n个元素。

方法二：

不使用递归进行全排列，用next_permutation函数先获得所有可能的出站顺序，将所有可能的顺序存到stackOut向量中，然后遍历所有可能的出站顺序，逐个判断当前出站顺序是否正确，如果正确则输出当前顺序。

具体做法：

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

bool visit[15]={0};
int step=0;
int n;
vector<int> stackIn;
vector<vector<int>> stackOut;

bool judge(vector<int> outOrder){//判断当前出站顺序是否符合题意
    stack<int> stk; 
    for(int in=0,out=0;in<=n;in++){
        stk.push(stackIn[in]);
        while(out<=n&&!stk.empty()&&stk.top()==outOrder[out]){//如果当前栈顶元素和出站顺序相同，则可以出站
            stk.pop();
            out++;
        }
    }
    return stk.empty();
} 

 
int main(){
    while(cin >> n){
        for(int i = 0; i < n; i++){
            int temp;
            cin>>temp;
            stackIn.push_back(temp);//输入进站顺序
        }
        vector<int> ans=stackIn;
        sort(ans.begin(), ans.end());
        do{
            stackOut.push_back(ans);
        }while(next_permutation(ans.begin(), ans.end())); //全排列
        for(int i = 0; i < stackOut.size(); i++){
            if(judge(stackOut[i])){ //判断排列的可行性
                for(auto it:stackOut[i]){//输出
                    cout << it << " ";
                }
                cout << endl;
            }
        }
    }
    return 0;
}

复杂度分析：

时间复杂度：O(n*n!)，遍历所有排列情况，每一种排列都需要花 $O (n)$ 时间去判断是否正确。
空间复杂度：O(n∗n!)，最坏情况下，全排列n!全部正确，每次有n个元素。

题解 | #火车进站#

题目的主要信息：

方法一：

方法二：