LeetCode 1114. 按序打印

约 8 分钟
文章信息 8 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节跳动 阿里巴巴 商汤
标签
多线程
目录

题目描述

✅ 1114. 按序打印

题意分析

同一个对象的三个方法 first、second、third 会分别被三个线程各调用一次，调用发生的先后顺序完全不可控。要求无论线程以什么顺序进入，最终打印出来的必须是 first、second、third 这个顺序。

「顺序不可控」是全部难点所在：不能假设 first 一定先被调用，也不能靠 sleep 之类的时间猜测去凑，只能靠线程间显式的同步信号建立「先行发生」关系。

需要表达的约束其实只有两条——second 必须在 first 打印完之后才能打印，third 必须在 second 打印完之后才能打印。两条约束彼此独立，因此两个一次性的同步信号就够了，不需要计数器加循环判断。

边界在于「等待必须是阻塞的而不是空转的」：用 while 循环反复读一个普通布尔变量既浪费 CPU，又因为缺少内存可见性保证而可能永远读到旧值。

解法：闭锁 / 通道同步

核心思路

最容易想到的是共享一个整型状态 step，second 反复检查 step == 1 才继续。这在功能上似乎可行，但有两处硬伤：一是忙等待会把 CPU 打满；二是普通变量没有可见性保证，写线程的修改可能长时间不被读线程看到，程序会卡死。加 volatile 能解决可见性，却仍然是自旋。

瓶颈在于用「反复查询」去表达「等待」。正确的抽象是让线程真正挂起，直到条件被满足时由对方唤醒。观察题目的约束结构：它是一条长度为 2 的依赖链，而且每个信号只需要被触发一次、之后永远保持已触发状态——这正是一次性闭锁（Java 的 CountDownLatch）和已关闭通道（Go 的 close(chan)）的语义。

于是设两个信号：firstDone 表示「first 已经打印完」，secondDone 表示「second 已经打印完」。约定的不变量是：firstDone 被释放，当且仅当 printFirst 已经执行结束；secondDone 被释放，当且仅当 printSecond 已经执行结束。

只要每个方法都遵循「先等待自己依赖的信号，打印，再释放自己的信号」这个次序，不变量就成立，而 await 与 countDown（或通道的接收与关闭）之间的 happens-before 关系保证了打印动作也随之被正确排序。

释放必须放在打印之后，这是最关键的一点。若先释放再打印，second 可能在 first 的打印语句真正执行完之前就开始打印，顺序仍然可能颠倒——信号表达的是「已完成」，不是「即将开始」。

一次性信号还带来一个常被忽视的好处：它对「等待发生在释放之后」这种情况天然安全。若 first 早就跑完，second 才进来，await 会立即返回而不是永久阻塞；Go 里已关闭的通道同样可以被无限次接收并立即返回。用无缓冲通道发送单个值就不具备这个性质。

解题步骤

  • 在对象里放两个同步信号，且用 final / 结构体字段的形式在构造时就初始化好。必须在构造函数里建好，因为三个线程可能在任意时刻进入方法，任何懒初始化都存在竞态。
  • first 不依赖任何前置条件，直接执行 printFirst.run()。
  • first 打印完成后释放 firstDone。放在打印之后，是为了让信号严格表示「打印已结束」这一事实。
  • second 进入后先等待 firstDone。这是阻塞等待而非轮询，线程会被挂起并让出 CPU，被唤醒时还能看到 first 线程在释放之前的全部写操作。
  • second 打印完成后释放 secondDone，把依赖链接到 third。
  • third 进入后等待 secondDone，随后打印。third 不需要再释放任何信号，因为没有后继者依赖它。

以最坏的调用顺序走一遍：假设线程 C 先调用 third，线程 B 再调用 second，线程 A 最后才调用 first。

线程 C 进入 third，等待 secondDone，此时计数仍为 1，C 被挂起。线程 B 进入 second，等待 firstDone，计数为 1，B 也被挂起。此刻两个线程都在阻塞，没有任何 CPU 空转。

线程 A 进入 first，无需等待，直接打印 "first"，随后 firstDone.countDown() 把计数减到 0。B 被唤醒，从 await 返回，打印 "second"，再 secondDone.countDown()。C 被唤醒，打印 "third"。最终输出为 first、second、third，符合要求。

再走一遍顺序相反的情形：线程 A 先跑完 first 并释放 firstDone，此时 B 才进入 second。B 调用 await 时计数已经是 0，方法立即返回不阻塞，打印 "second" 后释放 secondDone；C 同理立即通过。可见一次性信号在「先释放后等待」和「先等待后释放」两种时序下都正确，这正是选它而不是选无缓冲通道单次发送的原因。

代码实现

class Foo {
    private final java.util.concurrent.CountDownLatch firstDone = new java.util.concurrent.CountDownLatch(1);
    private final java.util.concurrent.CountDownLatch secondDone = new java.util.concurrent.CountDownLatch(1);

    public Foo() {}

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        firstDone.countDown();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        firstDone.await();
        printSecond.run();
        secondDone.countDown();
    }

    public void third(Runnable printThird) throws InterruptedException {
        secondDone.await();
        printThird.run();
    }
}

type Foo struct {
    firstDone  chan struct{}
    secondDone chan struct{}
}

func Constructor() Foo {
    return Foo{
        firstDone:  make(chan struct{}),
        secondDone: make(chan struct{}),
    }
}

func (f *Foo) first(printFirst func()) {
    printFirst()
    close(f.firstDone)
}

func (f *Foo) second(printSecond func()) {
    <-f.firstDone
    printSecond()
    close(f.secondDone)
}

func (f *Foo) third(printThird func()) {
    <-f.secondDone
    printThird()
}

复杂度分析

  • 时间复杂度：$O(1)$，每个方法只做一次阻塞等待和一次释放，与输入规模无关；线程被挂起的时间取决于调度而不计入算法复杂度。
  • 空间复杂度：$O(1)$，只维护两个固定的同步对象，通道用的是零字节的空结构体，不随调用次数增长。

关键点总结

  • 并发题的第一步永远是把「顺序要求」翻译成「依赖约束」：本题是一条 first → second → third 的链，链上有几条边就需要几个同步信号。
  • 信号必须在动作完成之后释放，语义是「我做完了」；提前释放会让后继者与前驱者的动作重叠，顺序保证瞬间失效。
  • 一次性、不可逆的同步原语（CountDownLatch(1)、close(chan)）比可重复的原语更适合「一次性事件」，因为它对等待与释放的先后时序天然免疫，不会因为等待来晚了而永久阻塞。
  • 忙等待循环即使加了 volatile 也只是「能跑对」，在面试里会被直接扣分，因为它把本该让出的 CPU 浪费掉了；阻塞等待才是标准答案。
  • 面试视角：面试官通常会让你说出至少两种实现并比较——CountDownLatch 最贴合语义，Semaphore(0) 用 acquire/release 同样自然，synchronized + wait/notifyAll 则必须配 while 循环防虚假唤醒。能主动指出「wait 必须在循环里」和「notify 要用 notifyAll」这两点，基本就答满了。

易错点总结

  • 错误写法：把释放写在打印之前，如 firstDone.countDown(); printFirst.run(); → 用例中 second 线程恰好在 first 打印语句执行前被唤醒，输出可能变成 second、first、third。
  • 错误写法：用普通布尔变量加 while (!flag) {} 自旋 → 没有可见性保证，等待线程可能永远读到缓存里的旧值，程序直接超时。
  • 错误写法：用 Thread.sleep(100) 猜测前一步已完成 → 判题机负载高时 first 可能还没跑完，second 就先打印，输出顺序随机出错，且这类 bug 无法稳定复现。
  • 错误写法：CountDownLatch 初始计数写成 0 → 用例中所有 await 立即返回，三个方法完全并发执行，顺序完全随机。
  • 错误写法：CountDownLatch 初始计数写成 2 却只 countDown 一次 → 用例中 second 永远等不到计数归零，程序死锁超时。
  • 错误写法：Go 里用 f.firstDone <- struct{}{} 发送而不是 close → 用例中若 second 先于 first 被调用，first 向无缓冲通道发送时无接收方会阻塞；更糟的是通道只能被接收一次，任何重复等待都会永久挂起。
  • 错误写法：Go 里在 Constructor 之外懒初始化通道，如在 first 里 f.firstDone = make(...) → 用例中 second 可能先读到 nil 通道，对 nil 通道接收会永久阻塞，直接死锁。
  • 错误写法：Java 里把 latch 声明为非 final 的静态字段 → 判题连续跑多个用例时，上一个用例已经归零的 latch 被复用，后续用例的 await 立即返回，顺序全乱。
  • 错误写法：用 synchronized + wait() 但不放在 while 循环里 → 虚假唤醒发生时线程会在条件仍未满足的情况下继续执行，输出顺序出错。
  • 错误写法：用 notify() 而不是 notifyAll() → 用例中唤醒的可能是 third 而不是 second，second 继续等待而 third 因条件不满足又回去等待，两个线程同时挂起造成死锁。
  • 错误写法：把两个信号合并成一个共享的计数器并让 second 和 third 都等它 → 用例中 second 和 third 的等待条件相同，两者会同时被放行，无法区分先后。

相似题目

题目 难度 考察点
1115. 交替打印 FooBar 中等 依赖关系是循环往复的，需要两个信号量互相唤醒 n 轮
1116. 打印零与奇偶数 中等 三个线程按 0、奇、0、偶的模式交替，信号分发要看当前数字奇偶
1195. 多线程 Fizz Buzz 中等 四个线程按整除条件分工，需要一个调度线程按序放行
1188. 设计有限阻塞队列 中等 生产者消费者模型，要同时处理队列满与队列空两个阻塞条件
1226. 哲学家进餐 中等 重点从排序变成防死锁，需要限制并发取叉数或打破循环等待