1279. 红绿灯路口

LeetCode：1279. Traffic Light Controlled Intersection
难度：简单
归类：并发、互斥锁、临界区保护
主解法：显式请求队列 + 处理标志，保证同一时刻只有一辆车通过路口

先给结论

把十字路口看作临界资源，同时只能有一辆车进入。用一个显式队列缓冲所有到达的车辆，再用一个处理循环逐个放行，保护整个"判断信号灯 → 必要时变灯 → 通过路口"的流程。

维护一个变量记录当前哪条路是绿灯（初始为 Road A），再维护一个请求队列。当一辆车到达时：

carArrived 只做一件事：把请求加入队列。
一个处理循环（processNext）逐个取出请求执行，同一时刻只有一辆车在临界区。
循环内：如果当前绿灯不在自己这条路，调用 turnGreen() 并更新记录，然后调用 crossCar() 让车通过。

JavaScript 是单线程事件循环，没有原生线程锁。"队列 + 单消费者"把并发到达的调用串行化，效果等价于 FIFO 互斥锁。

题目描述

有一个十字路口，两条路相交：

Road A（roadId = 1）：direction 1 为北向南，direction 2 为南向北。
Road B（roadId = 2）：direction 3 为西向东，direction 4 为东向西。

每条路在进入路口前有一盏交通灯，可以是绿灯或红灯：

绿灯：该条路上的车可以双向通过路口。
红灯：该条路上的车必须等待。

规则：

两盏灯不能同时为绿（A 绿则 B 红，B 绿则 A 红）。
初始状态：Road A 绿灯，Road B 红灯。
只有当车所在道路的灯为绿时，才能通过路口。
如果灯为红，必须先调用 turnGreen() 将灯变绿（同时另一条路自动变红）。
不允许无故调用 turnGreen()：如果当前路已经是绿灯，再调用会被判错。

你需要设计一个无死锁的交通灯控制系统。

核心思路

为什么需要锁

多辆车可能同时到达路口。如果不加控制，会出现以下竞态：

车 A（Road A）判断灯是绿的，正准备通过。
在同一时刻，车 B（Road B）判断灯也是绿的（因为车 A 还没变灯），也准备通过。
结果两辆车在路口相撞。

因此，"判断信号灯 → 变灯（如果需要）→ 通过"这三步必须是原子操作，同一时刻只能有一辆车执行。

JavaScript 如何实现互斥

JavaScript 没有 synchronized 或 pthread_mutex，但它是单线程事件循环。只要确保前一个车的完整逻辑执行完，再执行下一个车，就能达到互斥效果。

这里用显式队列 + 处理标志实现：

carArrived  →  queue.push(请求)；若没在跑就启动 processNext
processNext →  从队首取一辆执行；执行完用 setImmediate 调度下一步

要点有三个：

入队即返回。 carArrived 不执行通过逻辑，只登记请求，调用方永远不被阻塞。
单消费者。 只有 processNext 一个地方执行"判断灯 → 变灯 → 通过"，天然互斥；processing 标志保证任何时刻最多只有一个处理循环在跑。
异步接力。 每处理完一辆，用 setImmediate 把下一步调度到下一个事件循环 tick，而不是直接递归调用。这样无论队列里积了多少车，调用栈都不会随队列深度增长（避免栈溢出），期间新到达的车也能随时入队。

避免重复变灯

用 this.currentGreen 记录当前哪条路是绿灯。只有当 roadId !== this.currentGreen 时才调用 turnGreen()，满足题目"不能无故变灯"的要求。

代码实现

JavaScript 实现

class TrafficLight {
    constructor() {
        this.currentGreen = 1; // 初始 A 路绿灯
        this.queue = []; // 车辆请求队列
        this.processing = false; // 是否正在处理队列
    }

    /**
     * @param {number} carId 车辆编号
     * @param {number} roadId 所在道路 (1=A, 2=B)
     * @param {number} direction 行进方向 (本题未强制使用)
     * @param {function} turnGreen 使当前道路变绿的回调
     * @param {function} crossCar 让当前车通过的回调
     */
    carArrived(carId, roadId, direction, turnGreen, crossCar) {
        // 将请求加入队列
        this.queue.push({ roadId, turnGreen, crossCar });

        // 如果没有在处理，启动处理循环
        if (!this.processing) {
            this.processNext();
        }
    }

    processNext() {
        if (this.queue.length === 0) {
            this.processing = false;
            return;
        }

        this.processing = true;

        const { roadId, turnGreen, crossCar } = this.queue.shift();

        // 如果当前绿灯不是该车所在道路，才切换
        if (this.currentGreen !== roadId) {
            turnGreen(); // 切换绿灯
            this.currentGreen = roadId; // 更新状态
        }

        crossCar(); // 放行车辆

        // 异步处理下一辆车（避免递归堆栈溢出）
        setImmediate(() => this.processNext());
        // 也可用 setTimeout(this.processNext.bind(this), 0);
    }
}

代码与思路对照

阶段	对应代码	作用
记录绿灯方向	`this.currentGreen = 1`	初始 Road A 绿灯，避免无故调用 `turnGreen`
请求入队	`this.queue.push(...)`	到达即登记，调用方不被阻塞
启动保护	`if (!this.processing)`	保证任何时刻最多只有一个处理循环在跑
取出请求	`this.queue.shift()`	队首出队，FIFO 顺序处理
切换信号灯	`if (this.currentGreen !== roadId)`	只在需要变灯时才调用 `turnGreen()`
更新记录	`this.currentGreen = roadId`	记录当前哪条路是绿灯
通过路口	`crossCar()`	在独占保护下执行通过操作
异步接力	`setImmediate(() => this.processNext())`	下一步放到新的事件循环 tick，调用栈不随队列深度增长
排空退出	`this.processing = false`	队列清空后复位标志，下一辆车到达时能重新启动循环

正确性说明

互斥性。 通过逻辑只存在于 processNext 一处，且 processing 标志保证任何时刻最多一个处理循环在跑，因此不会有两辆车同时处于临界区。
正确变灯。 this.currentGreen 记录当前绿灯方向。如果车所在路已经是绿灯，不会调用 turnGreen()，满足题目约束。
无死锁。 队列 FIFO 出队，每辆登记过的车最终都会被取出处理；队列为空时标志复位，之后到达的车能重新启动循环，没有循环等待条件。
异常说明。 LeetCode 的 turnGreen / crossCar 不会抛异常。若要防御回调抛异常导致 processing 卡在 true、后续车辆无人处理，可以把取出请求后的执行包进 try / finally，在 finally 中继续调度下一步。

边界与陷阱

初始绿灯是 Road A： this.currentGreen 必须初始化为 1，否则第一辆 Road A 的车会错误地调用 turnGreen()。
队列排空要复位标志： 忘记 this.processing = false，之后到达的车会认为循环还在跑，永远等不到处理。
用 shift 而不是 pop： 从队首取车才是 FIFO；从队尾取会变成后进先出，先到的车可能饥饿。
不能直接同步递归： processNext 末尾若直接调用自身，调用栈深度会随队列长度增长，大量车辆到达时栈溢出；用 setImmediate / setTimeout(..., 0) 把下一步调度到新 tick。
不能无故调用 turnGreen()： 必须通过 this.currentGreen 判断，当前路已经是绿灯时跳过。
临界区必须集中在消费者一处： "判断绿灯 → 变灯 → 通过"都要在 processNext 内完成，不能让 carArrived 各自执行。

复杂度分析

设总共到达 n 辆车：

时间复杂度：O(n)。每辆车只执行一次临界区逻辑，锁的等待和释放都是 O(1)。
额外空间复杂度：O(n)。最坏情况下所有车同时到达，队列中会堆积 n 个待处理的请求。

面试官递进追问

1. 为什么需要锁？只记录绿灯方向不够吗？

不够。在多线程/并发环境中，"判断绿灯 → 通过路口" 是两步操作。如果没有锁，可能多个线程同时判断为绿灯并同时通过，造成竞态。锁保证这两步原子化。

2. JavaScript 是单线程的，为什么还需要锁？

LeetCode 的测试框架会并发调用 carArrived（例如通过多个 Worker 或快速连续调用）。虽然 JS 引擎是单线程，但这些调用产生的异步回调可能交错执行。队列 + 处理标志把通过逻辑收敛到唯一的消费者循环中串行执行，避免状态判断和更新的竞态。

3. 如果不用显式队列，还有其他实现方式吗？

可以用 Promise 链，把每辆车的通过任务依次接到链尾：

constructor() {
    this.currentGreen = 1;
    this.chain = Promise.resolve();
}

carArrived(...) {
    this.chain = this.chain.then(() => {
        if (this.currentGreen !== roadId) {
            turnGreen();
            this.currentGreen = roadId;
        }
        crossCar();
    });
    return this.chain;
}

Promise 的语义保证链上任务串行执行，逻辑与显式队列等价。写法更短，但"链即锁"不如"队列 + 处理循环"直观，而且任务抛异常会让链进入 rejected 状态、后续车辆被跳过。

4. 如果`turnGreen` 或`crossCar` 是异步的，代码需要怎么改？

如果它们是返回 Promise 的异步函数，把 processNext 改为 async，在调用处加 await，等异步操作完成后再调度下一步：

async processNext() {
    // ...取出请求
    if (this.currentGreen !== roadId) {
        await turnGreen();
        this.currentGreen = roadId;
    }
    await crossCar();
    setImmediate(() => this.processNext());
}

await 保证当前车的异步操作彻底完成后，下一辆车才开始处理。

5. 这个锁是公平锁吗？

是。队列用 shift 从队首取车，先调用 carArrived 的车先被处理，不会出现"后来的车先通过"的饥饿现象。

常见错误

队列排空后忘记把 processing 复位为 false，之后到达的车辆永远无人处理。
用 pop 代替 shift 取车，把公平队列变成后进先出。
processNext 末尾直接同步递归调用自身，大量车辆时调用栈溢出。
锁的范围太小，只保护 crossCar() 而没有保护 turnGreen() 和状态更新。
初始 currentGreen 设错，导致所有车都触发一次 turnGreen()。
每次调用 carArrived 都调用 turnGreen()，不管当前是否已经是绿灯。

可迁移总结

临界区保护： 并发环境中，读取共享状态 + 根据状态执行操作必须原子化。
显式队列： JavaScript 中用"请求队列 + 单消费者循环"就能把并发调用串行化，等价于 FIFO 互斥锁。
状态缓存： 记录当前状态（如绿灯方向），避免重复操作（如重复变灯）。
异步接力： 处理循环的下一步用 setImmediate 调度，调用栈深度与队列长度解耦。
一句话记忆： 入队即返回，单消费者逐个放行，绿灯不对才变灯。

刷题后自测

先只回答第 1 题，再展开后续问题：

为什么 this.currentGreen 的读取和修改也必须在 processNext 内完成？

为什么 processNext 结尾用 setImmediate 调度下一步，而不是直接递归调用 this.processNext()？

如果测试框架用 setTimeout 随机延迟调用 carArrived，队列版本还能保证正确性吗？为什么？

写出 Promise 链版本的 carArrived，并分析与显式队列版本在异常处理上的差异。

#1279. 红绿灯路口

#先给结论

#题目描述

#核心思路

#为什么需要锁

#JavaScript 如何实现互斥

#避免重复变灯

#代码实现

#JavaScript 实现

#代码与思路对照

#正确性说明

#边界与陷阱

#复杂度分析

#面试官递进追问

#1. 为什么需要锁？只记录绿灯方向不够吗？

#2. JavaScript 是单线程的，为什么还需要锁？

#3. 如果不用显式队列，还有其他实现方式吗？

#4. 如果turnGreen 或crossCar 是异步的，代码需要怎么改？

#5. 这个锁是公平锁吗？

#常见错误

#可迁移总结

#刷题后自测