LLD 案例 3：电梯系统

为什么电梯题难

停车场和 LRU 的核心是数据结构，电梯题的核心是状态和调度：电梯在时间上不断变化，请求随时到达，多部电梯还要协作。很多候选人类图画得不错，却说不清“电梯此刻该往哪走”。

需求澄清

• 几部电梯、几层楼？（假设 N 部电梯，M 层）
• 两类请求：楼层外呼（hall call，只带方向：上或下）和轿厢内选层（car call，带目标楼层）。
• 优化目标：平均等待时间，还是公平、不饿死？（通常先保证不饿死，再优化等待）
• 需要处理载重、维护模式、消防模式吗？（先列为扩展）
• 是做按时间推进的模拟，还是只设计调度逻辑？

核心实体

关键是把分派（哪部电梯来响应）和单梯调度（这部电梯按什么顺序停）分开。这是两个不同的问题，混在一个类里是最常见的失分点。

单梯状态机

flowchart LR
  accTitle: 单梯状态机
  idle["IDLE"] -->|"有目标"| moving["MOVING"]
  moving -->|"到达目标层"| doors["DOORS_OPEN"]
  doors -->|"还有目标"| moving
  doors -->|"没有目标"| idle
  any["任意状态"] -->|"维护指令"| maint["MAINTENANCE"]

用 enum 表示状态，转换逻辑集中在一个地方（比如 step()），不要散落在各处的 if 判断里。

单梯调度：LOOK 算法

电梯调度的经典思路来自磁盘调度的 SCAN/LOOK：沿当前方向一路服务到底，该方向没有请求了再掉头。它避免了按到达顺序服务时电梯来回乱跑，也保证不会饿死某一层。

用两个有序集合存停靠目标，按“在哪个方向上经过时停”分类，而不是按“在当前层上方还是下方”：

upStops   : 上行途中要停的层（向上的外呼 + 要往上去的内选）
downStops : 下行途中要停的层（向下的外呼 + 要往下去的内选）

当前在 5 楼向上，upStops = {7, 9}，downStops = {3, 1}
路径: 5 → 7 → 9 → 掉头 → 3 → 1

为什么不能只按楼层高低分？电梯在 5 楼上行，7 楼有人按了“下”。如果只看楼层，7 会被放进 upStops，电梯上行途中在 7 楼开门，接到一个要下楼的人，他只能先跟着上到 9 楼再下来。正确的规则是：

• 外呼按方向入队；
• 同方向、在前方的外呼，在本趟服务；
• 反方向的外呼，留到掉头之后再服务。

TreeSet<Integer> upStops = new TreeSet<>();     // 上行途中要停的层
TreeSet<Integer> downStops = new TreeSet<>();   // 下行途中要停的层

void addHallCall(int floor, Direction want) {   // 外呼：按乘客要去的方向入队
    (want == Direction.UP ? upStops : downStops).add(floor);
}

void addCarCall(int floor) {                    // 内选：按相对当前层的位置入队
    if (floor > current) upStops.add(floor);
    else if (floor < current) downStops.add(floor);
    else openDoors();
}

boolean workAbove() { return upStops.higher(current) != null || downStops.higher(current) != null; }
boolean workBelow() { return upStops.lower(current) != null || downStops.lower(current) != null; }

void step() {                                   // 每个 tick 调用一次
    if (dir == Direction.UP && !workAbove()) dir = workBelow() ? Direction.DOWN : Direction.IDLE;
    else if (dir == Direction.DOWN && !workBelow()) dir = workAbove() ? Direction.UP : Direction.IDLE;
    else if (dir == Direction.IDLE) dir = workAbove() ? Direction.UP : workBelow() ? Direction.DOWN : Direction.IDLE;

    if (dir == Direction.IDLE) {                // 别处没活：只处理本层的请求
        if (upStops.remove(current) | downStops.remove(current)) openDoors();
        return;
    }

    current += (dir == Direction.UP) ? 1 : -1;
    boolean stop = (dir == Direction.UP) ? upStops.remove(current) : downStops.remove(current);
    if (dir == Direction.UP && !workAbove()) stop |= downStops.remove(current);   // 最高点：接向下的外呼
    if (dir == Direction.DOWN && !workBelow()) stop |= upStops.remove(current);   // 最低点：接向上的外呼
    if (stop) openDoors();
}

step() 先定方向：沿当前方向前方还有活（两个集合里任何一个有前方的楼层）就继续；没有了才掉头；两边都没有就空闲。然后移动一层，只在方向对得上的停靠点开门：上行时停 upStops，下行时停 downStops。唯一的例外是这一趟的最远点：比如上行时最高的目标是 9 楼的一个向下外呼，电梯到 9 楼就停下接人，然后掉头。开门停留的计时在这里省略。

注意 upStops 里可能有当前层以下的楼层（比如电梯在 5 楼，2 楼有人按了“上”），它要等电梯下到 2 楼、准备折返向上时才服务。所以判断“前方还有没有活”要同时看两个集合。

多梯分派：打分函数

外呼来了，分给谁？给每部电梯算一个代价，选最小的：

interface DispatchStrategy {
    Elevator choose(List<Elevator> cars, HallCall call);
}

把它做成策略接口有真实理由：早高峰（大家都从一楼往上）和平峰期的最优策略不同，楼宇管理方可能需要切换。更精细的代价函数会估算“到达该层之前还要停几次”，因为每次停靠开关门要好几秒，比移动一层耗时得多。

并发模型

请求来自很多按钮，是并发到达的；电梯本身在时间里连续运行。两种模型：

1. 共享状态 + 锁：每部电梯的停靠集合加锁，按钮线程直接调用 addHallCall / addCarCall，电梯线程执行 step 时也要加锁。
2. 消息传递：每部电梯一个线程（或事件循环）加一个请求队列。外部只往队列里投请求，电梯线程独占自己的状态。

推荐第二种：电梯的状态只被一个线程修改，step() 里不需要任何锁，推理起来简单得多。Dispatcher 读取电梯状态时用快照即可——稍微过时的位置信息不影响正确性，只影响分派质量。

flowchart LR
  accTitle: 按钮、分派器和每部电梯的线程
  btn["按钮"] --> sys["ElevatorSystem"] --> disp["Dispatcher"]
  disp --> q1["请求队列"] --> car1["电梯线程 1"]
  disp --> q2["请求队列"] --> car2["电梯线程 2"]

扩展讨论

• 来不来得及停：电梯在两层之间高速运行时，新加一个“下一层”的停靠点，可能已经刹不住了。真实系统会算出当前还能停下的最近楼层，比它更近的请求当作已经错过，留到下一趟。上面的 tick 模型每 tick 只移动一层，相当于假设总能停住，面试时口头点明即可。
• 重新分派：分配后电梯故障或长时间被占用，外呼要能转给别的电梯。
• 消防模式：所有电梯回到一楼，停止响应外呼。这是状态机里的一个新状态，正好体现状态集中管理的好处。
• 分区：高层建筑里低区和高区电梯分开服务。

常见失分点

• 把分派和单梯调度写进一个类，几百行 if-else。
• 只用一个队列按到达顺序服务，电梯来回乱跑。
• 忽视外呼的方向，上行途中为一个要下楼的外呼停车。
• 说不清并发请求如何安全地交给电梯。