题解 | #火车进站#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    let n = +await readline();
    let input = await readline();
    input = input.split(' ').map(i => +i);
    let res = [];
    res = sol(n, input);
    res = res.map(arr => {
        for(let i = 1; i <= n; i++){
            let index = arr.indexOf(i);
            arr.splice(index,1);
        }
        return arr;
    })
    res.sort();
    for(let arr of res){
        console.log(arr.join(' '));
    }
}()

/**
 * params n {number} 车辆总数
 * params input {array} 车辆入站次序
 */
function sol(n, input){
    if(n === 1){
        return [[input[0], input[0]]];
    }
    let res = [];
    for(let arr of sol(n - 1, input.slice(0, n))){
        let index = arr.indexOf(input[n - 2]);
        for(let j = index + 1; j <= arr.length; j++){
            let temp = [...arr];
            temp.splice(j, 0, input[n - 1], input[n - 1])
            res.push(temp)
        }
    }
    return res
}

这个解法也是看的别人的，原答案是python写的，他的描述我看懂了一半。另一半是按照代码的逻辑在草稿纸上走了一遍才懂的。现在对照我的JavaScript版本进行一个梳理。

原题解是将车辆的入站出站操作放在同一个数组中进行分析的，在数组中序号第一次出现表示车辆入站，第二次表示车辆出站。

在以上基础下，题解中提到几点：

1. 入站序列中的最后一个，他的入站和出站操作必定是连在一起的（因为最后一辆车入站之后再没有车入站了，需要等他出站之后之前入站的车辆才能出站）。
2. 最后一辆车的入站出站操作可以在他前一辆车入站之后任意时刻进行（emmm就是这里没太懂），下面通过两个具体的例子说明。

当只有一辆车的时候，车辆的入站序列为 [2] ,车辆进出站的操作序列为：[2, 2]，表示2号车先进站再出站，符合第一点。

当有两辆车的时候，比如入站的序列为[2, 1]，我们需要求的是入站顺序为2号车先入站，1号车再入站的情况下，所有可能的出站顺序。结合上述第一点可知，在所有的操作集合中，1号车的入站出站操作一定是连续的，可以将其视作一个整体。当2号车入站之后有两种情况：1、2号车出站，2/2号车不出站，结合上述第二点，1号车的出入站操作可以在2号车出站之前或者之后进行。那么整个车辆出入栈的序列为：[2, 1, 1, 2]、[2, 2, 1, 1]。其实就是将最后一辆车的操作插入在前一辆车入站之后的操作空隙里面。

在得到操作序列之后将入站操作去掉（从操作序列中删除每个第一次出现的序号）就得到了所有出站顺序