题解 | #火车进站#

HJ77火车进站

一.题目描述

给出一组序列，请求输出其所有的出栈的合法序列。

二.算法二(暴力)

开始看到题目感觉很熟悉却又很懵，该怎么去判断出栈顺序呢？我们不妨想到无论怎么样，出栈的顺序一定被包含于所给数列的全排列中，所以问题就转换为了怎么去判断一个序列是不是合法的出栈序列？

对于如何判断序列是不是合法的出栈序列我们有了一定认识，下面给出完整的代码和注释：

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int st[N],a[N];
int n;
bool check(){
    stack<int>s;
    int cnt=1;
    for(int i=1;i<=n;i++){
        s.push(a[i]);
        //栈顶元素和出栈元素相等 下标后移一位
        while(s.size()&&st[cnt]==s.top()){
            s.pop();
            cnt++;
        }
    }
    if(s.size()){
        return false;
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i]=a[i];
    }
    //需要对a进行全排列，先对其进行排序
    sort(st+1,st+1+n);
    do{
        if(check()){
            for(int i=1;i<=n;i++){
                cout<<st[i]<<" ";
            }
            cout<<endl;
        }
    } while(next_permutation(st+1,st+1+n));//利用next_permutation实现全排列
    return 0;
}

时间复杂度：$O(n\mathrm{\ast }n!)O(n\ast n!)$，全排列的复杂度为$O(n!)O(n!)$，所以时间复杂度是$O(n\mathrm{\ast }n!)O(n\ast n!)$。

空间复杂度：$O(n)O(n)$，需要空间来存储全排练的数列。

三.算法二(dfs搜索)

前面我们是依赖于next_permutation函数来实现全排练，我们也可以用dfs来构建全排列，每次都有着两个分支，要么实现出栈，要么实现入栈，每次操作完都需要回溯才能够实现检查全排列，如果某一种输出长度到了n说明这种序列结束了，可以输出。但是由于遍历过程中存在重复的现象，我们可以使用set去重，然后输出，下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
int n;
//now表示当前序列中的顺序
//num表示入栈顺序
//st表示栈的情况
//mp用来去重和储存所有的出栈序列
//idex用来表示入栈序列的下标
//n表示排列需要到达的数目
void dfs(vector<int>& num,stack<int> st,vector<int> now,set<vector<int>> &mp,int idex,int &n){
    if(now.size() == n){
        mp.insert(now);
        return;
    }
    for(int i=1;i<=2;i++){
        //对于栈的两种选择
        if(i==1){//出栈
            if(!st.empty()){
                int ans = st.top();
                st.pop();
                now.push_back(ans);
                dfs(num,st,now,mp,idex,n);
                //回溯
                st.push(ans);
                now.pop_back();
            }

        }else if(i==2){//入栈
            if(idex<n){
                int ans=num[idex];
                st.push(ans);
                idex++;
                dfs(num,st,now,mp,idex,n);
                idex--;
                st.pop();
            }

        }
    }
}
int main(){
        cin>>n;
        vector<int> num(n);
        set<vector<int> > mp;
        stack<int> st;
        vector<int> now;
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        st.push(num[0]);
        dfs(num,st,now,mp,1,n);
    //输出set去重后的排序
        for(auto it=mp.begin();it!=mp.end();it++){
            for(int i=0;i<n;i++){
                cout << (*it)[i] << " ";
            }
            cout<<endl;
        }
    return 0;
}

时间复杂度：$O(n!log2(n!))O(n!log2(n!))$，dfs遍历整个全排列，最坏情况下全排列都要输出，那么时间复杂度就达到了$O(n!log2(n!))O(n!log2(n!))$。

空间复杂度：$O(n\mathrm{\ast }n!)O(n\ast n!)$,set集合存储序列