题解 | #火车进站#

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 = [];
    let stack = [];
    let outStack = [];
    backtrace(n, res, input, stack, outStack);
    res.sort()
    for(let arr of res){
        console.log(arr.join(' '));
    }
}()


function backtrace(n, res, inSeq, stack, outSeq){
    if(outSeq.length === n){
        res.push([...outSeq]);
        return;
    }
    // 车站为空，待入站的序列不为空，则入栈
    if(stack.length === 0 && inSeq.length !== 0){
        stack.push(inSeq.shift());
        backtrace(n, res, inSeq, stack, outSeq);
    }else if(stack.length !== 0 && inSeq.length === 0){
        // 待入站序列为空表明所有火车都已进站，则不再有入站操作，顺序出栈
        outSeq.push(stack.pop());
        backtrace(n, res, inSeq, stack, outSeq);
    }else if(stack.length !== 0 && inSeq.length !== 0){
        // 车站和待入站序列都不为空，则既可入站也可出栈
        let tempIn = [...inSeq];
        let tempStack = [...stack];
        let tempOut = [...outSeq];
        // 入站
        stack.push(inSeq.shift());
        backtrace(n, res, inSeq, stack, outSeq);
        // 回溯
        inSeq = tempIn;
        stack = tempStack;
        outSeq = tempOut;
        // 出站
        outSeq.push(stack.pop());
        backtrace(n, res, inSeq, stack, outSeq);
    }
}

没有什么思路，看的别人的解法。

主要维护了三个数组inSeq、stack、outSeq。

数组inSeq主要存储入站的次序，stack表示已进站的车辆次序，是个栈，outSeq存储出栈的次序。

出入栈的操作分为三种情况：

1. 车站stack是空的，inSeq不为空，此时没有车辆能够出栈，只能进行入站操作。
2. 车站stack不为空，inSeq是空的，此时没有车辆能够入站，只能进行出站操作。
3. 车站stack不为空，inSeq不为空，此时既可以入站也可以出站。此时需要进行回溯来完成两种操作。

• 入站操作：从inSeq队首取出元素，加入到stack栈顶
• 出站操作：从stack栈顶弹出元素加入到outSeq队尾
• 当outSeq长度等于车辆总数时，表明得到一种出站次序，可加入到结果集合中。