LeetCode-Go 题解632. Smallest Range Covering Elements from K ListsK 个升序列表的最小区间滑动窗口 频次统计【免费下载链接】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长度相同取左端点更小者。示例 1Input: [[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 用户传入类型已修改为ListListInteger重置代码模板后可以看到此项改动。1.3 题目大意中文你有k个升序排列的整数数组。找到一个最小区间使得k个列表中的每个列表至少有一个数包含在其中。二、核心思路将多列表问题归约到滑动窗口原题解文档给出的关键洞察是本题是 LeetCode 76 题Minimum Window Substring的变种版。76 题要求在母字符串S中找到能包含字符串T全部字符的最小子串本题则要求从k个升序列表中各取一个元素拼出一个覆盖集合并求其最小区间。二者的归约关系如下对比维度76. Minimum Window Substring632. Smallest Range本题数据形态字符整数母序列字符串S把k个列表合并后排序的大数组目标集合T的全部字符k个列表中每个列表各出一个元素窗口约束窗口包含T的所有字符窗口覆盖全部k个列表编号求值目标最短子串长度最短且左端点最小的区间由于题目要求每个列表至少贡献一个元素而合并排序后元素的原始归属列表编号信息会丢失因此必须维护每个元素所在的列表编号index。这正是 632 题相比 76 题的关键增量。经过上述转换即可完全套用 76 题的滑动窗口模板。仓库中的 76 题实现 76. Minimum Window Substring.go 使用的正是同一套双指针 频次计数结构可以对照阅读详见本文第五节。三、滑动窗口解法详解3.1 算法步骤展开并编号遍历k个列表把每个元素包装成{val, index}二元组index为元素所属列表编号全部追加进一个大数组numList按值排序将numList按val升序排序。排序后任意连续子区间[left, right]都对应值域上的一个连续窗口双指针滑动left初始为 0right初始为 -1当窗口尚未覆盖全部k个列表count len(nums)且右指针未越界时不断右移right扩窗并用freqMap记录窗口内各列表编号的出现频次一旦count k窗口已覆盖所有列表记录当前窗口值域numList[right].val - numList[left].val与历史最优比较并更新答案随后左移left收缩窗口同步更新freqMap与count直到窗口再次不满足覆盖条件继续扩窗终止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 right1 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.InterfaceLen/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频次 mapmap[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)保证每个元素都能作为窗口左端点被考察right1 len(numList)防止右指针越界。4.1 示例运行推演对[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]展开并编号得到 14 个element列表编号分别为 0、1、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 个列表的窗口为[0, 5]值域差 5随后持续收缩/扩张最终记录的最优窗口为[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 right1 len(s) count len(t) { // 右指针扩窗更新频次与 count right } else { // 窗口满足条件时记录答案随后左指针收缩 if right-left1 minW count len(t) { ... } left } }两者的差异仅在于76 题用固定大小数组[256]int统计字符频次632 题用map[int]int统计列表编号频次76 题答案更新条件是窗口长度right-left1632 题是值域差numList[right].val - numList[left].val76 题直接在字符串上滑动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 测试命令。七、小结与延伸总结本题要点问题本质求覆盖k个列表的最小值域区间属于覆盖性最小区间类问题核心归约展开元素并绑定列表编号 → 按值排序 → 在排序序列上跑双指针滑动窗口把多列表问题变成 76 题同款单序列滑动窗口关键技巧用freqMap维护各列表在窗口内的出现频次以count k作为覆盖完成的判定条件复杂度时间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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：632. Smallest Range Covering Elements from K Lists（K 个升序列表的最小区间，滑动窗口 + 频次统计）
LeetCode-Go 题解632. Smallest Range Covering Elements from K ListsK 个升序列表的最小区间滑动窗口 频次统计【免费下载链接】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长度相同取左端点更小者。示例 1Input: [[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 用户传入类型已修改为ListListInteger重置代码模板后可以看到此项改动。1.3 题目大意中文你有k个升序排列的整数数组。找到一个最小区间使得k个列表中的每个列表至少有一个数包含在其中。二、核心思路将多列表问题归约到滑动窗口原题解文档给出的关键洞察是本题是 LeetCode 76 题Minimum Window Substring的变种版。76 题要求在母字符串S中找到能包含字符串T全部字符的最小子串本题则要求从k个升序列表中各取一个元素拼出一个覆盖集合并求其最小区间。二者的归约关系如下对比维度76. Minimum Window Substring632. Smallest Range本题数据形态字符整数母序列字符串S把k个列表合并后排序的大数组目标集合T的全部字符k个列表中每个列表各出一个元素窗口约束窗口包含T的所有字符窗口覆盖全部k个列表编号求值目标最短子串长度最短且左端点最小的区间由于题目要求每个列表至少贡献一个元素而合并排序后元素的原始归属列表编号信息会丢失因此必须维护每个元素所在的列表编号index。这正是 632 题相比 76 题的关键增量。经过上述转换即可完全套用 76 题的滑动窗口模板。仓库中的 76 题实现 76. Minimum Window Substring.go 使用的正是同一套双指针 频次计数结构可以对照阅读详见本文第五节。三、滑动窗口解法详解3.1 算法步骤展开并编号遍历k个列表把每个元素包装成{val, index}二元组index为元素所属列表编号全部追加进一个大数组numList按值排序将numList按val升序排序。排序后任意连续子区间[left, right]都对应值域上的一个连续窗口双指针滑动left初始为 0right初始为 -1当窗口尚未覆盖全部k个列表count len(nums)且右指针未越界时不断右移right扩窗并用freqMap记录窗口内各列表编号的出现频次一旦count k窗口已覆盖所有列表记录当前窗口值域numList[right].val - numList[left].val与历史最优比较并更新答案随后左移left收缩窗口同步更新freqMap与count直到窗口再次不满足覆盖条件继续扩窗终止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 right1 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.InterfaceLen/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频次 mapmap[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)保证每个元素都能作为窗口左端点被考察right1 len(numList)防止右指针越界。4.1 示例运行推演对[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]展开并编号得到 14 个element列表编号分别为 0、1、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 个列表的窗口为[0, 5]值域差 5随后持续收缩/扩张最终记录的最优窗口为[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 right1 len(s) count len(t) { // 右指针扩窗更新频次与 count right } else { // 窗口满足条件时记录答案随后左指针收缩 if right-left1 minW count len(t) { ... } left } }两者的差异仅在于76 题用固定大小数组[256]int统计字符频次632 题用map[int]int统计列表编号频次76 题答案更新条件是窗口长度right-left1632 题是值域差numList[right].val - numList[left].val76 题直接在字符串上滑动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 测试命令。七、小结与延伸总结本题要点问题本质求覆盖k个列表的最小值域区间属于覆盖性最小区间类问题核心归约展开元素并绑定列表编号 → 按值排序 → 在排序序列上跑双指针滑动窗口把多列表问题变成 76 题同款单序列滑动窗口关键技巧用freqMap维护各列表在窗口内的出现频次以count k作为覆盖完成的判定条件复杂度时间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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
