题解 | #火车进站#

#include <bits/stdc++.h>
//火车站只有一个方向进出 ---- 栈
using namespace std;

vector<vector<int>> res;
vector<int> path;

void backtracking(vector<int>& nums, vector<bool> used){
    //终止条件
    if(path.size() == nums.size()){
        res.push_back(path);
    }
    
    for(int i = 0; i < nums.size(); i++){
        if(used[i]) continue;
        
        used[i] = true;
        path.push_back(nums[i]);
        backtracking(nums, used); //
        
        path.pop_back();
        used[i] = false;
    }
}

//全排列 ：LeetCode 46. 全排列
vector<vector<int>> permute(vector<int>& nums) {
    if(nums.empty()) return res;
    
    vector<bool> used(nums.size(), false);
    backtracking(nums, used);
    
    return res;
}

// //根据入栈序列vec 判断 出栈序列tmp是否正确
bool check(vector<int> vec, vector<int> tmp){
    stack<int> st;
    int i = 0, j = 0;
    for(i = 0; i < vec.size(); i++){
        //依次将原始数组入栈
        st.push(vec[i]);
        //如果栈顶元素等于出栈序列元素，则栈顶元素出栈并出栈序列下标加一
        while(j < vec.size() && !st.empty() && tmp[j] == st.top()){ 
            //依次判断tmp中每个序列的值是否与栈顶相等
            st.pop();
            j++;
        }
    }
    
    return st.empty(); //
}

int main(){
    int n = 0;
    while(cin >> n){
        vector<int> vec(n, 0);
        for(int i = 0; i < n; i++){
            int num = 0;
            cin >> num;
            vec[i] = num;
        }
        
        //法一
        vector<int> tmp = vec; //开一个临时数组，做全排列 next_permutation
        sort(tmp.begin(), tmp.end());
        do{
//             全排列
//             for(int i = 0; i < tmp.size(); i++){
//                 cout << tmp[i] << "";
//             }
//             cout << endl;
            
            if(check(vec, tmp)){
                for(int i = 0; i < n; i++){
                    cout << tmp[i] << " "; //cout << tmp[i] << " \n"[i == tmp.size() - 1];
                }
                cout << endl;
            }
        }while(next_permutation(tmp.begin(), tmp.end())); //自动会按照字典序排序输出 全排列结果
        
        
        /*//法二
        //牛客网会超时
        vector<int> tmp = vec; //开一个临时数组，做全排列 permute(tmp)
        sort(tmp.begin(), tmp.end()); //先排序
        vector<vector<int>> quanPaiLie = permute(tmp);
        for(int j = 0; j < quanPaiLie.size(); j++){
            vector<int> tmp = quanPaiLie[j];
            if(check(vec, tmp)){
                for(int i = 0; i < n; i++){
                    cout << tmp[i] << " "; //cout << tmp[i] << " \n"[i == tmp.size() - 1];
                }
                cout << endl;
            }
        }*/
    }
    
    return 0;
}