LeetCode LCR 115. 序列重建
目录
题目描述
题意分析
题目目标：给定一个原始序列 org，以及若干条子序列 seqs，判断 org 是否是「唯一」能同时满足所有 seqs 作为其子序列的那个序列。换句话说，要同时验证两件事——org 确实是一个合法解，并且合法解只有它一个。
核心约束：这里的重点不在于「能不能重建」，而在于「重建结果唯一不唯一」。seqs 里的每条子序列只提供了相邻元素之间的先后关系，这是典型的偏序信息；把元素当节点、把「谁必须排在谁前面」当有向边，问题立刻变成图上的拓扑排序。而拓扑序唯一的充要条件是众所周知的：整个排序过程中，任意时刻入度为 0 的节点都恰好只有一个——一旦某一步同时有两个节点可选，就至少存在两个不同的合法拓扑序，唯一性被破坏。第二个信号是 seqs 中的元素可能超出 org 的范围，也可能覆盖不全 org 的所有元素，两种情况都会导致答案为 false，因此必须先做节点集合的规模核对。
边界处理：seqs 可能为空或只含空序列，此时没有任何约束信息，除非 org 也为空否则无法唯一确定；seqs 中可能出现重复的相邻对，重复建边会让入度被多加，必须去重；seqs 中可能出现 org 里没有的数字，或者遗漏了 org 中的某些数字；图中可能存在环，此时拓扑排序无法输出全部节点，同样应判 false；某条 seq 可能只有一个元素，它不产生任何边但确实贡献了一个节点。
解法：拓扑排序判唯一
核心思路
最先想到的可能是逐条验证：对每条 seq 检查它是不是 org 的子序列，全部通过就返回 true。但这只解决了「org 是合法解」这一半，完全没有回答「有没有别的序列也合法」。举例来说，org = [1,2,3] 与 seqs = [[1,2],[1,3]] 时每条都是子序列，可 [1,3,2] 同样满足所有约束，答案应当是 false。瓶颈就在于：验证合法性是局部的，而验证唯一性必须站在全局的约束图上看。
把视角切换到图。seqs 中每一条序列 $[v_1, v_2, \dots, v_k]$ 实际上给出了 k-1 条硬性的先后关系：$v_1$ 必须在 $v_2$ 之前，$v_2$ 必须在 $v_3$ 之前，依此类推。注意不需要给不相邻的元素之间连边，因为先后关系具有传递性，相邻边已经蕴含了全部信息，多连边只会增加代价。这样得到一张有向图，所有满足约束的排列恰好就是这张图的全部拓扑序。于是「唯一重建」等价于「拓扑序存在且唯一，并且那个唯一的拓扑序等于 org」。
唯一性的判定依赖一个经典结论：在基于入度的拓扑排序过程中，若每一步可选的入度为 0 的节点都恰好只有一个，则拓扑序唯一；只要某一步有两个及以上候选，就能通过交换它们的先后顺序构造出另一个合法拓扑序。因此维护的状态是一个候选队列，不变量是：队列中始终存放当前所有前驱已全部就绪、可以立即输出的节点。算法每轮先检查队列规模是否恰好为 1，不为 1 立刻否定；再把唯一的候选取出，与 org 当前位置比对，不一致同样否定；然后把它的所有后继入度减一，减到 0 的入队。整个过程结束后，还要确认输出的节点总数等于 org 的长度——若小于，说明图里有环或有节点始终无法就绪。至于节点集合的核对（seqs 覆盖的元素恰好构成 org 的元素集合），可以在建图前用一次规模比较加上后续逐位比对来共同保证。
解题步骤
- 第一步：扫一遍 seqs，把出现过的所有元素登记进节点集合，并为每个节点初始化空的邻接集合与 0 入度。 为什么要先把节点全部登记好再建边：如果边和节点混在一起处理，某个只出现在边终点的节点可能还没有入度记录就被自增，导致后续读取时找不到键。为什么用集合而不是数组存邻接：seqs 中同一对相邻元素可能反复出现，用集合能天然去重。
- 第二步：比较节点集合的规模与 org 的长度，不相等直接返回 false。 为什么这一步不可省：若 seqs 覆盖的元素比 org 少，说明有元素完全不受约束，它可以放在多个位置，唯一性必然不成立；若比 org 多，说明出现了 org 之外的数字，org 根本不是合法重建结果。这个检查用一次比较就排除了两类失败情形。
- 第三步：再扫一遍 seqs，对每条序列的每一对相邻元素 (a, b) 建有向边 a→b，只有当这条边是首次出现时才把 b 的入度加一。 为什么只连相邻对：先后关系可传递，$v_1 \to v_2 \to v_3$ 已经蕴含 $v_1$ 在 $v_3$ 之前，额外连 $v_1 \to v_3$ 不增加任何约束却会把边数从 $O(L)$ 抬到 $O(L^2)$。为什么必须去重后再加入度：重复边会让 b 的入度被多加，导致它的前驱全部处理完后入度仍大于 0，永远无法入队，算法会误判为有环而返回 false。
- 第四步：把所有入度为 0 的节点放进队列，并准备一个指向 org 的游标 idx。 为什么初始入度为 0 的节点就是起点候选：入度为 0 意味着没有任何元素被要求排在它前面，它可以立即输出。
- 第五步：循环处理队列，每轮先判断队列规模是否为 1，不是则返回 false。 为什么规模大于 1 就否定：此刻有多个节点都可以合法地放在当前位置，任选其一都能得到一个完整的拓扑序，唯一性被破坏。为什么不需要单独处理规模为 0：循环条件本身就是队列非空，进入循环时规模至少为 1。
- 第六步：取出唯一候选，与
org[idx]比对，不同则返回 false，相同则 idx 前进一位。 为什么要逐位比对而不是最后整体比较：提前发现不一致可以立即短路，避免无谓计算；同时这一步也顺带保证了 seqs 涉及的元素值与 org 的元素值完全一致——只要有一个值对不上就会在这里被抓住。为什么要先判idx >= org.length：防御性写法，避免在异常数据下越界读取。- 第七步：把出队节点的所有后继入度减一，减到 0 的入队。 为什么减到 0 才入队：入度代表还有多少个前驱没被输出，归零才说明所有约束都已满足，此时它才真正可选。为什么每条边只触发一次减操作：邻接集合已经去重，遍历一遍就等于恰好处理每条边一次。
- 第八步：循环结束后返回
idx == org.length。 为什么还要这个收尾判断：如果图中存在环，环上的节点入度永远无法归零，队列会提前变空，此时 idx 小于 org 的长度，应当返回 false。只有把所有节点都成功输出且每一步都唯一、每一步都与 org 吻合，才能确认答案为 true。- 以
org = [1,2,3], seqs = [[1,2],[1,3]]走一遍。 第一遍扫描登记节点 {1,2,3}，规模 3 等于 org 长度 3，通过检查。建边：从 [1,2] 得 1→2，2 的入度变为 1；从 [1,3] 得 1→3，3 的入度变为 1。入度为 0 的只有节点 1，入队。第一轮循环：队列规模为 1，取出 1，与org[0] = 1一致，idx 变为 1；处理 1 的后继 2 和 3，两者入度都减为 0，双双入队，此时队列里有两个节点。第二轮循环：队列规模为 2，不等于 1，立即返回 false。这正是期望结果——[1,3,2] 也满足所有子序列约束，重建不唯一。再看一个应当返回 true 的用例org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]：节点集合仍是 {1,2,3}，规模匹配。建边 1→2、1→3、2→3，入度分别为 1: 0、2: 1、3: 2。初始队列只有 1。第一轮：规模为 1，取出 1 与org[0]一致，idx = 1；后继 2 入度减为 0 入队，后继 3 入度减为 1 仍不入队，队列只剩 2。第二轮：规模为 1，取出 2 与org[1] = 2一致，idx = 2；后继 3 入度减为 0 入队。第三轮：规模为 1，取出 3 与org[2] = 3一致，idx = 3；3 没有后继。队列变空退出，idx 等于 org 长度 3，返回 true。整个过程中每一步都恰好只有一个可选节点，说明拓扑序唯一，且这个唯一序列正是 org。
代码实现
// 队列中每一轮必须只有一个候选，并且要与 org 的当前位置一致。
class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
Set<Integer> nodes = new HashSet<>();
for (List<Integer> seq : seqs) {
for (int v : seq) {
nodes.add(v);
graph.putIfAbsent(v, new HashSet<>());
indegree.putIfAbsent(v, 0);
}
}
if (nodes.size() != org.length) {
return false;
}
for (List<Integer> seq : seqs) {
for (int i = 1; i < seq.size(); i++) {
int a = seq.get(i - 1);
int b = seq.get(i);
if (graph.get(a).add(b)) {
indegree.put(b, indegree.get(b) + 1);
}
}
}
Queue<Integer> queue = new ArrayDeque<>();
for (int v : nodes) {
if (indegree.get(v) == 0) {
queue.offer(v);
}
}
int idx = 0;
while (!queue.isEmpty()) {
if (queue.size() != 1) {
return false;
}
int cur = queue.poll();
if (idx >= org.length || cur != org[idx]) {
return false;
}
idx++;
for (int next : graph.get(cur)) {
indegree.put(next, indegree.get(next) - 1);
if (indegree.get(next) == 0) {
queue.offer(next);
}
}
}
return idx == org.length;
}
}
// 队列中每一轮必须只有一个候选，并且要与 org 的当前位置一致。
func sequenceReconstruction(org []int, seqs [][]int) bool {
graph := make(map[int]map[int]struct{})
indeg := make(map[int]int)
nodes := make(map[int]struct{})
for _, seq := range seqs {
for _, v := range seq {
nodes[v] = struct{}{}
if _, ok := graph[v]; !ok {
graph[v] = make(map[int]struct{})
}
if _, ok := indeg[v]; !ok {
indeg[v] = 0
}
}
}
if len(nodes) != len(org) {
return false
}
for _, seq := range seqs {
for i := 1; i < len(seq); i++ {
a := seq[i-1]
b := seq[i]
if _, ok := graph[a][b]; !ok {
graph[a][b] = struct{}{}
indeg[b]++
}
}
}
queue := make([]int, 0)
for v := range nodes {
if indeg[v] == 0 {
queue = append(queue, v)
}
}
idx := 0
head := 0
for head < len(queue) {
if len(queue)-head != 1 {
return false
}
cur := queue[head]
head++
if idx >= len(org) || cur != org[idx] {
return false
}
idx++
for next := range graph[cur] {
indeg[next]--
if indeg[next] == 0 {
queue = append(queue, next)
}
}
}
return idx == len(org)
}
复杂度分析
- 时间复杂度：$O(V + E)$，其中 V 是不同元素的个数、E 是去重后的相邻对数量，两者都被 seqs 的总长度界住。凭什么：建图阶段对 seqs 扫描两遍，每个元素和每对相邻元素各被处理常数次；拓扑排序阶段每个节点恰好出队一次、每条边恰好被松弛一次，队列操作和哈希查找均摊都是常数。
- 空间复杂度：$O(V + E)$。凭什么：邻接表存下所有去重后的边，入度表和节点集合各占 $O(V)$，队列中同时存在的节点数不超过 V，此外只有常数个标量。
关键点总结
- 「先后关系」类的约束一律翻译成有向边，问题就落进拓扑排序的框架。识别信号是题目给的信息形如「A 必须在 B 之前」，而不管它以序列、字典序还是依赖列表的形式出现。
- 拓扑序唯一的判据是「每一步入度为 0 的节点恰好一个」，这是本题区别于普通拓扑排序题的核心。理解它的方式是：候选多于一个时，交换任意两个候选的输出顺序都能得到另一个合法序，唯一性立刻被反例推翻。
- 只连相邻元素的边，靠传递性覆盖其余关系。这不仅是效率优化——把边数从 $O(L^2)$ 降到 $O(L)$——也是正确性的一部分，因为多余的边不会改变拓扑序集合却会显著增加去重负担。
- 建边必须去重后再累加入度。入度的语义是「还有多少个不同的前驱未就绪」，重复计数会让节点永远无法归零，把一个本该成立的用例误判为有环。
- 判定题要把所有失败通道列全再动手：节点集合规模不符、某步候选多于一个、某步与 org 不匹配、结束时未输出全部节点。漏掉任何一条都会在特定用例上翻车，这种「穷举失败条件」的习惯在面试中比写对主流程更能体现严谨性。
- 面试视角：这题是拓扑排序的进阶考法，面试官期待你先说出「约束建图 + 拓扑排序」的框架，再主动补上唯一性判据。常见追问有三个——「为什么不需要连非相邻元素」（传递性）、「重复边为什么必须去重」（入度语义）、「如果只问能否重建而不问唯一怎么办」（去掉队列规模检查即可，退化成标准拓扑排序）。
易错点总结
- 错误写法：只验证每条 seq 是不是 org 的子序列就返回 true。用例
org = [1,2,3], seqs = [[1,2],[1,3]]→ 两条都是子序列于是返回 true，但 [1,3,2] 同样合法，正确答案是 false。- 错误写法：建边时不去重，直接对每对相邻元素给入度加一。用例
org = [1,2], seqs = [[1,2],[1,2]]→ 节点 2 的入度被加到 2，节点 1 出队后只减到 1，队列提前变空，idx 停在 1，误返回 false，正确答案是 true。- 错误写法：省掉节点集合规模与 org 长度的比较。用例
org = [1,2,3], seqs = [[1,2]]→ 节点 3 从未出现却也从未被检查，拓扑排序输出 [1,2] 后队列变空，虽然收尾的idx == org.length仍能兜住返回 false，但换成org = [1,2], seqs = [[1,2],[1,2],[3,4]]这类含额外元素的数据时，若没有规模检查就会在比对阶段才发现问题，逻辑链条不清晰且容易写出漏判分支。- 错误写法：不检查队列规模，只做标准拓扑排序再和 org 整体比较。用例
org = [1,2,3], seqs = [[1,2],[1,3]]→ 队列中 2 和 3 的出队顺序取决于容器实现，可能恰好得到 [1,2,3] 而返回 true，正确答案是 false。- 错误写法：为「保险」把每条 seq 中所有元素两两连边。用例 一条长度为 1000 的 seq → 边数从 999 暴涨到约五十万，去重开销和内存双双上升，在多条长序列下直接超时。
- 错误写法：循环结束后直接返回 true，不检查 idx 是否走完 org。用例
org = [1,2], seqs = [[1,2],[2,1]]→ 图中存在环 1→2→1，两个节点入度都为 1，初始队列为空，循环一次都不进就返回 true，正确答案是 false。- 错误写法：把入度减到 0 的判断写成小于等于 0。用例 存在重复边且未去重的数据 → 同一节点可能被多次入队，队列规模检查失效，还会重复输出同一个元素。
- 错误写法：遍历后继时直接修改入度表却同时用增强 for 遍历邻接集合并向其中添加元素。用例 任意含分支的图 → Java 抛 ConcurrentModificationException，Go 中对 map 边遍历边写入行为未定义。
- 错误写法：假设元素值就是 1 到 n 的连续整数并用数组下标存入度。用例
seqs = [[100, 200]]→ 数组越界崩溃，题目并未保证取值范围紧凑，必须用哈希表或先做离散化。- 错误写法：比对时写成
cur == org[idx]且 cur 与 org 元素都是 Integer 包装类型。用例 元素值超过 128 如org = [1000, 2000]→ 比较的是对象引用而非数值，恒为假，返回 false。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 207. 课程表 | 中等 | 只判断有无环，不要求输出序列，是拓扑排序的最简形态 |
| 210. 课程表 II | 中等 | 需要输出任意一个合法拓扑序，不涉及唯一性判定 |
| 269. 火星词典 | 困难 | 边要从相邻单词的首个不同字符推导，还要识别前缀矛盾这一非法输入 |
| 310. 最小高度树 | 中等 | 无向图上的逐层剥叶，展示入度思想在非有向场景下的变体 |
| 面试题 04.01. 节点间通路 | 中等 | 同为有向图问题但只问可达性，用搜索即可，不需要入度统计 |