C站车厢调度问题 - 使用栈判断车厢能否按照指定顺序驶出

"因此，驶入 C 站的车厢必须按照相反的顺序驶出。 Qingyong进一步限定允许的操作如下：\n\n让 A 方向最前面的车厢从 B 方向驶出车站；\n让 A 方向最前面的车厢驶入中转站 C；\n让中转站 C 中最后驶入的车厢从 B 方向驶出车站。\n请帮助Qingyong判断能否让车厢按照站长给定的顺序驶出北京北站。\n\n输入数据\n第一行为一个正整数 n，代表车厢总数，n < 100000。 第二行有 n 个正整数，代表站长要求的车厢驶出车站顺序\n解析：这个问题可以用栈来解决。我们用一个栈来模拟中转站 C，用一个变量来表示下一个要驶出的车厢号。\n我们遍历站长要求的车厢驶出顺序，如果当前车厢号等于下一个要驶出的车厢号，说明可以直接驶出，将下一个要驶出的车厢号加1。\n否则，我们判断中转站 C 是否为空，如果不为空且栈顶元素等于下一个要驶出的车厢号，说明可以从中转站 C 驶出，将栈顶元素弹出，将下一个要驶出的车厢号加1。\n否则，将当前车厢号入栈。\n最后，如果栈中剩余的元素可以按照顺序驶出，返回"YES"；否则，返回"NO"。\n\n代码如下：\n\ndef canDriveOut(n, order):\n stack = []\n nextCar = 1\n for car in order:\n if car == nextCar:\n nextCar += 1\n elif stack and stack[-1] == nextCar:\n stack.pop()\n nextCar += 1\n else:\n stack.append(car)\n while stack:\n if stack.pop() != nextCar:\n return "NO"\n nextCar += 1\n return "YES"\n\n# 测试\nprint(canDriveOut(5, [5, 4, 1, 2, 3])) # YES\nprint(canDriveOut(5, [4, 5, 3, 2, 1])) # NO\n