LeetCode-Go 题解：632. Smallest Range Covering Elements from K Lists（K 个升序列表的最小区间，滑动窗口 + 频次统计）

LeetCode-Go 题解：632. Smallest Range Covering Elements from K Lists（K 个升序列表的最小区间，滑动窗口 + 频次统计）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文基于 LeetCode-Go 仓库中 0632 题官方题解文档，完整讲解 LeetCode 632 题「Smallest Range Covering Elements from K Lists」的题意、约束与滑动窗口解法，并对照仓库内 Go 实现源码 与 单元测试 进行逐行剖析。读完本文，你将掌握如何把「多列表覆盖最小区间」问题归约到经典滑动窗口模型（76 题思路），并能够在自己的 Go 项目中复用该模板解决同类区间覆盖问题。

一、题目概述

1.1 题目原文

给定k个按升序排列的整数列表，找出一个最小区间，使得该区间内至少包含每个列表中的一个数字。

区间[a, b]比区间[c, d]"更小" 的定义为：

• b - a < d - c（区间长度更短）；或
• 当b - a == d - c时，a < c（长度相同取左端点更小者）。

示例 1：

Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] Output: [20,24]

解释：

• 列表 1：[4, 10, 15, 24, 26]，其中24落在[20,24]内；
• 列表 2：[0, 9, 12, 20]，其中20落在[20,24]内；
• 列表 3：[5, 18, 22, 30]，其中22落在[20,24]内。

1.2 题目约束

• 列表可能包含重复元素，因此"升序"实际表示非严格递增，即>=；
• 1 <= k <= 3500；
• -10^5 <= 元素值 <= 10^5；
• 对于 Java 用户：传入类型已修改为List<List<Integer>>，重置代码模板后可以看到此项改动。

1.3 题目大意（中文）

你有k个升序排列的整数数组。找到一个最小区间，使得k个列表中的每个列表至少有一个数包含在其中。

二、核心思路：将多列表问题归约到滑动窗口

原题解文档给出的关键洞察是：本题是 LeetCode 76 题（Minimum Window Substring）的变种版。

76 题要求在母字符串S中找到能包含字符串T全部字符的最小子串；本题则要求从k个升序列表中各取一个元素，拼出一个"覆盖集合"并求其最小区间。二者的归约关系如下：

由于题目要求"每个列表至少贡献一个元素"，而合并排序后元素的原始归属列表编号信息会丢失，因此必须维护每个元素所在的列表编号（index）。这正是 632 题相比 76 题的关键增量。经过上述转换，即可完全套用 76 题的滑动窗口模板。

仓库中的 76 题实现 76. Minimum Window Substring.go 使用的正是同一套双指针 + 频次计数结构，可以对照阅读（详见本文第五节）。

三、滑动窗口解法详解

3.1 算法步骤

1. 展开并编号：遍历k个列表，把每个元素包装成{val, index}二元组（index为元素所属列表编号），全部追加进一个大数组numList；
2. 按值排序：将numList按val升序排序。排序后，任意连续子区间[left, right]都对应"值域"上的一个连续窗口；
3. 双指针滑动：
   • left初始为 0，right初始为 -1；
   • 当窗口尚未覆盖全部k个列表（count < len(nums)）且右指针未越界时，不断右移right扩窗，并用freqMap记录窗口内各列表编号的出现频次；
   • 一旦count == k（窗口已覆盖所有列表），记录当前窗口值域numList[right].val - numList[left].val，与历史最优比较并更新答案；
   • 随后左移left收缩窗口，同步更新freqMap与count，直到窗口再次不满足覆盖条件，继续扩窗；
4. 终止：left遍历完整个大数组后，res中保存的即为最小区间。

3.2 复杂度分析

• 展开 + 排序：设n为所有列表元素总数，排序耗时O(n log n)；
• 双指针扫描：left、right各最多移动n次，整体线性O(n)；
• 总时间复杂度：O(n log n)；
• 空间复杂度：O(n)，主要开销在展开后的元素数组与频次 map。

注意：题解文档中给出的时间/空间复杂度是O(n*log n)与O(n)，其前提正是先展开合并、再排序、最后滑动扫描的流程。

四、Go 源码逐行剖析

仓库实现位于 632. Smallest Range Covering Elements from K Lists.go，核心代码如下：

func smallestRange(nums [][]int) []int { numList, left, right, count, freqMap, res, length := []element{}, 0, -1, 0, map[int]int{}, make([]int, 2), math.MaxInt64 for i, ns := range nums { for _, v := range ns { numList = append(numList, element{val: v, index: i}) } } sort.Sort(SortByVal{numList}) for left < len(numList) { if right+1 < len(numList) && count < len(nums) { right++ if freqMap[numList[right].index] == 0 { count++ } freqMap[numList[right].index]++ } else { if count == len(nums) { if numList[right].val-numList[left].val < length { length = numList[right].val - numList[left].val res[0] = numList[left].val res[1] = numList[right].val } } freqMap[numList[left].index]-- if freqMap[numList[left].index] == 0 { count-- } left++ } } return res }

逐行解读关键设计：

• element{val, index}结构：val保存元素值，index保存所属列表编号，二者绑定后参与排序，保证排序后仍能识别"覆盖了哪些列表"。
• sort.Sort(SortByVal{numList})：通过自定义SortByVal类型实现sort.Interface（Len/Swap/Less），按val升序排序，见文件末尾的辅助类型定义：

type element struct { val int index int } type elements []element func (p elements) Len() int { return len(p) } func (p elements) Swap(i, j int) { p[i], p[j] = p[j], p[i] } type SortByVal struct{ elements } func (p SortByVal) Less(i, j int) bool { return p.elements[i].val < p.elements[j].val }

• freqMap（频次 map）：map[int]int，键是列表编号，值是该列表在当前窗口内的元素出现次数。它是判断"窗口是否覆盖全部k个列表"的唯一依据：
  • 右指针扩窗时，若freqMap[index] == 0说明该列表首次进入窗口，count++；
  • 左指针收缩时，若freqMap[index]减到 0，说明该列表从窗口消失，count--。
• 覆盖判定与答案更新：count == len(nums)表示窗口已覆盖全部k个列表，此时窗口值域为numList[right].val - numList[left].val，与length（初始为math.MaxInt64）比较，严格小于才更新res，天然满足题目"长度相同时取更小左端点"的优先级（因为左端点更小的窗口会先被记录，且只有在更短时才覆盖）。
• 边界处理：right初始为 -1、left初始为 0，循环条件left < len(numList)保证每个元素都能作为窗口左端点被考察；right+1 < len(numList)防止右指针越界。

4.1 示例运行推演

对[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]：

1. 展开并编号得到 14 个element（列表编号分别为 0、1、2）；
2. 按值排序后序列为：0(1), 4(0), 5(2), 9(1), 10(0), 12(1), 15(0), 18(2), 20(1), 22(2), 24(0), 26(0), 30(2)；
3. 双指针滑动过程中，第一个满足覆盖全部 3 个列表的窗口为[0, 5]（值域差 5），随后持续收缩/扩张；
4. 最终记录的最优窗口为[20, 24]：值域差 4，且 20（列表 2）、22（列表 2 之外实际来自列表 2 的 20、列表 3 的 22、列表 1 的 24）分别覆盖三个列表，验证输出[20, 24]。

五、与 76 题滑动窗口模板的对照

仓库中 76. Minimum Window Substring.go 的骨架与 632 完全同构：

for left < len(s) { if right+1 < len(s) && count < len(t) { // 右指针扩窗，更新频次与 count right++ } else { // 窗口满足条件时记录答案，随后左指针收缩 if right-left+1 < minW && count == len(t) { ... } left++ } }

两者的差异仅在于：

• 76 题用固定大小数组[256]int统计字符频次，632 题用map[int]int统计列表编号频次；
• 76 题答案更新条件是窗口长度right-left+1，632 题是值域差numList[right].val - numList[left].val；
• 76 题直接在字符串上滑动，632 题需要先展开 + 排序构造"值域上的连续窗口"。

掌握了这个模板，76、632 以及同类"覆盖性最小区间"问题可以一网打尽。两题的完整题目与解法思路可对照阅读 76 题题解文档。

六、测试用例验证

仓库为本题提供了单元测试 632. Smallest Range Covering Elements from K Lists_test.go，结构上使用para632（输入[][]int）与ans632（期望输出[]int）封装：

func Test_Problem632(t *testing.T) { qs := []question632{ { para632{[][]int{{4, 10, 15, 24, 26}, {0, 9, 12, 20}, {5, 18, 22, 30}}}, ans632{[]int{20, 24}}, }, } for _, q := range qs { _, p := q.ans632, q.para632 fmt.Printf("【input】:%v 【output】:%v\n", p, smallestRange(p.one)) } }

测试用官方示例验证了smallestRange的输出为[20, 24]。这也是 LeetCode-Go 仓库"100% test coverage"工程规范的一部分，新增用例只需在qs切片中追加{para632{...}, ans632{...}}即可。运行方式：在仓库根目录执行go test ./leetcode/0632.Smallest-Range-Covering-Elements-from-K-Lists/ -v（仓库根目录的 go.mod 已声明模块，可直接使用 Go 测试命令）。

七、小结与延伸

总结本题要点：

1. 问题本质：求覆盖k个列表的最小值域区间，属于"覆盖性最小区间"类问题；
2. 核心归约：展开元素并绑定列表编号 → 按值排序 → 在排序序列上跑双指针滑动窗口，把多列表问题变成 76 题同款单序列滑动窗口；
3. 关键技巧：用freqMap维护各列表在窗口内的出现频次，以count == k作为覆盖完成的判定条件；
4. 复杂度：时间O(n log n)（排序主导），空间O(n)。

从源码结构看，本题是仓库滑动窗口专题的经典代表，同目录下还有大量采用相同"展开 + 排序 + 双指针"或"map 频次统计"模式的题解，可作为横向扩展阅读（参见仓库根目录 README.md 中的题目索引表，632 题位于 Hard 难度分组）。读者在面试或工程中遇到"多个有序序列求覆盖最小区间/最短子数组"类需求时，可直接套用本文模板。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go