LeetCode 1114. 按序打印

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

题目描述

✅ 1114. 按序打印

image-20260928225804389

image-20260928225804390

题意分析

同一个 Foo 实例被三个线程共享，三个线程分别调用 first、second、third 各一次。线程可能以任意顺序开始执行，但三个打印回调必须严格按照第一、第二、第三的顺序完成。

不能假设先创建或先启动的线程就先得到调度，也不能用固定休眠时间猜测顺序。要控制的是各次打印之间的先后依赖，而不是把输入数字排序后在一个方法里替其他线程打印。

解法：闭锁 / 通道同步

核心思路

[!blue]

三个阶段形成两条依赖：第二次打印需要等待第一次完成，第三次打印需要等待第二次完成。因此准备两个初始未完成的信号，分别表示 firstDone 和 secondDone，不需要让三个线程争抢一个“谁先执行”的锁。

first 没有前置条件，直接执行打印，回调返回后释放第一个信号。second 必须先等待第一个信号，再执行自己的打印，完成后释放第二个信号。third 等第二个信号后才打印。每条信号都只会在前驱打印之后产生，所以两条依赖串起来，就保证了完整输出顺序。

Java 用计数初始为一的 CountDownLatch：await() 等待计数归零，countDown() 将完成状态打开。Go 用创建好的无缓冲通道：后继在通道上接收，前驱在打印后关闭通道，使等待接收可以继续。这里发送的是“已经完成”的事件，不需要传递具体数据。

完成状态会保留下来。即使前驱先执行完、后继很晚才开始等待，闭锁已经归零或通道已经关闭，后继仍可立即继续，不会因为错过通知而永久阻塞。两个同步对象必须在构造时就初始化，并由三个方法共享。

这是一轮一次性的顺序执行：每个方法只调用一次，打印回调正常完成。闭锁和关闭的通道不复位，不用于反复轮转打印；Go 的同一通道也不能重复关闭。

解题步骤

  1. 构造对象时，初始化两个尚未完成的闭锁或通道。
  2. first 执行自己的打印回调，返回后发出第一次完成信号。
  3. second 先等待第一次完成，再执行自己的打印，最后发出第二次完成信号。
  4. third 等待第二次完成后执行自己的打印。
  5. 每个线程只负责自己的回调，同步对象保证先后顺序。

代码实现

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)。只使用两个固定的同步对象。

关键点总结

[!green]

  • 信号代表打印完成，通知必须放在回调之后。
  • 两条前驱完成依赖就能约束三个阶段，无需依赖线程启动顺序。
  • 一次性完成状态支持先通知后等待，不会丢失已经发生的完成事件。
  • 所有方法共享构造时创建的信号，而不是各自临时创建同步对象。

易错点总结

[!yellow]

  • 先通知再打印：后继可能立即被调度，抢在前驱打印完成之前输出。
  • 信号初始已经放行：后继无需等待就会执行，失去顺序约束。
  • 依靠线程启动顺序或休眠时间：操作系统调度不保证这种时序。
  • 在方法执行中才初始化通道：提前到达的后继可能已经阻塞在 nil 通道上，必须在构造时完成初始化。
  • 把同一个对象用于多轮打印：已有信号不会重新关闭等待，重复关闭 Go 通道还会报错；当前协议按题目只执行一轮。

相似题目

题目 难度 关联与区别
1115. 交替打印 FooBar 中等 原题需要重复交替，本题只执行一次固定顺序，阶段信号的复用方式不同。
1116. 打印零与奇偶数 中等 原题由三个线程按0、奇数、偶数规则持续交接，本题只需保证first、second、third先后。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/68965145
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！