最小区间

记住这句:堆里永远是「每个列表当前指针的一个值」共 k 个,堆顶最小值当区间左端、curMax 当区间右端。每一轮拿当前窗口去刷新最优答案,然后把最小的那一路指针往后挪、压入下一个值。某个列表没有下一个值时就停下。

先建堆。把每个列表的第一个数都放进小顶堆。L0 的首个值 4 入堆,当前窗口最大值 curMax = 4。

L1 的第一个数 0 入堆。同时更新窗口最大值:curMax = 4。堆里现在有 2 个值,正是 2 路指针各指一个。

L2 的第一个数 5 入堆。同时更新窗口最大值:curMax = 5。堆里现在有 3 个值,正是 3 路指针各指一个。

三路起点都进堆了:堆顶最小 0、窗口最大 5,起始候选区间是 [0, 5],宽 5。它已经覆盖三个列表,只是还很宽,接下来一步步把左端往右收。

第一轮:堆顶最小是 0(来自 L1),窗口右端是 curMax = 5,宽度 5。这比之前最优更短,刷新最优为 [0, 5]。

弹出最小的 0,把 L1 的指针往后挪一格,压入它的下一个值 9。它比原 curMax 5 还大,窗口右端被它顶到 curMax = 9。新堆顶最小是 4,窗口收成了 [4, 9]。

第二轮:堆顶最小是 4(来自 L0),窗口 [4, 9] 宽度 5,不比已知最优 [0, 5] 短,最优保持不动。

弹出最小的 4,把 L0 的指针往后挪一格,压入它的下一个值 10。它比原 curMax 9 还大,窗口右端被它顶到 curMax = 10。新堆顶最小是 5,窗口收成了 [5, 10]。

第三轮:堆顶最小是 5(来自 L2),窗口 [5, 10] 宽度 5,不比已知最优 [0, 5] 短,最优保持不动。

弹出最小的 5,把 L2 的指针往后挪一格,压入它的下一个值 18。它比原 curMax 10 还大,窗口右端被它顶到 curMax = 18。新堆顶最小是 9,窗口收成了 [9, 18]。

第四轮:堆顶最小是 9(来自 L1),窗口 [9, 18] 宽度 9,不比已知最优 [0, 5] 短,最优保持不动。

弹出最小的 9,把 L1 的指针往后挪一格,压入它的下一个值 12。它不超过 curMax 18,窗口右端 curMax 维持 18。新堆顶最小是 10,窗口收成了 [10, 18]。

第五轮:堆顶最小是 10(来自 L0),窗口 [10, 18] 宽度 8,不比已知最优 [0, 5] 短,最优保持不动。

弹出最小的 10,把 L0 的指针往后挪一格,压入它的下一个值 15。它不超过 curMax 18,窗口右端 curMax 维持 18。新堆顶最小是 12,窗口收成了 [12, 18]。

第六轮:堆顶最小是 12(来自 L1),窗口 [12, 18] 宽度 6,不比已知最优 [0, 5] 短,最优保持不动。

弹出最小的 12,把 L1 的指针往后挪一格,压入它的下一个值 20。它比原 curMax 18 还大,窗口右端被它顶到 curMax = 20。新堆顶最小是 15,窗口收成了 [15, 20]。

第七轮:堆顶最小是 15(来自 L0),窗口 [15, 20] 宽度 5,不比已知最优 [0, 5] 短,最优保持不动。

弹出最小的 15,把 L0 的指针往后挪一格,压入它的下一个值 24。它比原 curMax 20 还大,窗口右端被它顶到 curMax = 24。新堆顶最小是 18,窗口收成了 [18, 24]。

第八轮:堆顶最小是 18(来自 L2),窗口 [18, 24] 宽度 6,不比已知最优 [0, 5] 短,最优保持不动。

弹出最小的 18,把 L2 的指针往后挪一格,压入它的下一个值 22。它不超过 curMax 24,窗口右端 curMax 维持 24。新堆顶最小是 20,窗口收成了 [20, 24]。

第九轮:堆顶最小是 20(来自 L1),窗口右端是 curMax = 24,宽度 4。这比之前最优更短,刷新最优为 [20, 24]。

要缩短区间必须把最小的 20 往后挪,可它来自 L1,而 L1 已经到末尾、没有下一个值可补。一旦弹掉它,堆里就缺了 L1 这一路,剩下的 [22, 24] 不再覆盖全部列表、不是有效窗口。所以停在最后一个有效窗口,最终答案 = [20, 24]。

回头看整条路径:我们从没枚举任何区间,只是反复「读 k 路的最小值与最大值得到一个候选窗口、刷新最优、再把最小值所在的那一路推进一格」。最小值一路右移,窗口左端越收越紧,直到某路到头无法再补。最终最短区间 = [20, 24],宽度 4。

单列表取首个最小元素、公共值给零宽区间、单元素列表须横跨全部点、有负数照常,这些边界想清就稳。

两个高频追问:与合并 K 个升序链表同骨架、以及排序加滑窗的等价解法。