企业官网建设流程全解析

LeetCode 632 题目

题号：632 题目名称：最小区间 Smallest Range Covering Elements from K Lists（Hard）

题目描述

你有k个非递减排列的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数字包含在这个区间内。

区间比较规则：
如果b-a < d-c，则区间[a,b]比[c,d]更小；
如果区间长度相等，左端点更小的区间更小。

示例1

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]

解释：
列表1：24 在区间 [20,24]
列表2：20 在区间 [20,24]
列表3：22 在区间 [20,24]

示例2

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

约束条件

• 1 ≤ k ≤ 3500
• 每个列表长度 ≥ 1
• -10^5 ≤ 元素 ≤ 10^5

费曼学习法讲解破解过程

费曼：假装讲给零基础小白，用生活化比喻，拆解思路，找到卡点。

通俗理解题目

比喻：三家店铺，每家店铺有一份从小到大排好的商品价格清单。
我们要找一个价格范围[L,R]，每家店至少有一件商品落在这个价格区间里面。并且要求这个价格范围尽可能窄；如果宽度一样，选起点更小的区间。

核心观察

1. 所有子数组本身已经升序，这是本题最重要的条件，我们要充分利用。
2. 任何一个合法区间，一定是由从每个数组挑选一个数字组成，区间左=选中数字最小值，区间右=选中数字最大值。
3. 贪心策略：我们维护从每个数组取出1个元素，这k个元素构成候选区间；每次把k个里面最小的那个换掉，取它所在数组的下一个更大的值，再形成新区间，不断更新最优答案。

为什么这个贪心成立？
当前区间的短板是最小值。想要缩小区间，只能把最小值变大（数组升序，下一个元素更大）；最大值只能不变或者变大。一旦某个数组没有下一个元素，算法停止，没法继续构造新候选区间。

两种主流解法

解法一：最小堆（优先队列）【最优解法，面试首选】

✅ 时间复杂度 O(N logk)，N是全部元素总数，k是列表数量；空间 O(k)
思路步骤：

1. 初始化：每个数组拿出第一个元素放进小顶堆；同时记录这k个元素里的最大值cur_max。
2. 堆里面存三元组：(数值，所属列表编号，该元素在列表中的下标)
3. 循环：
   ① 弹出堆里最小元素cur_min；此时候选区间就是[cur_min, cur_max]，对比更新全局最优区间。
   ② 看这个最小元素所在数组后面还有没有元素：
   - 有：取出下一个元素，推入堆，更新cur_max（新元素可能更大），继续循环。
   - 没有：直接终止循环！因为这个数组再也拿不出更大元素，无法再凑齐k个元素构成合法区间。
4. 返回最优区间。

卡点解释：为什么数组用完就停？
我们必须保证堆里永远有每个列表恰好一个元素，才能保证区间覆盖全部k个列表。一旦某列表元素耗尽，再也凑不出满足条件的候选区间，直接退出。

解法二：合并全部元素 + 滑动窗口（双指针+哈希计数）

✅ 时间复杂度 O(N logN)，N是全部元素；空间O(N)
思路步骤：

1. 把所有元素拆成(value, 原列表编号)，拼成一个大列表，按value排序。
2. 滑动窗口left、right，right不断向右扩张窗口。
3. 哈希表记录窗口内，每个列表编号出现次数；记录窗口覆盖了多少个不同列表cover_cnt。
4. 当cover_cnt == k，窗口满足条件，尝试移动left缩小窗口，更新最小区间；直到窗口不再覆盖全部k个列表。

类比：LeetCode76 最小覆盖子串。把“字符”换成“列表编号”。
缺点：需要存储全部元素，数据量大时内存更高；优点：堆不熟的时候容易联想最小覆盖子串。

暴力解法（仅理解，不推荐，会超时）

枚举从每个数组挑选一个元素的全部组合，算出区间，记录最小。组合爆炸，k很大直接超时。

应用场景举例

1. 传感器多源数据采集：k个传感器，每个传感器按时间采集一组有序测量值，找一个最短时间窗口，每个传感器至少有一条数据落在窗口内；用于多传感器时间对齐。
2. 多供应商价格筛选：多家供应商的产品报价有序列表，找最小价格区间，每家至少有一款产品在区间内，采购筛选。
3. 推荐系统：多个分类的有序推荐分数，找分数区间，每个分类至少一个推荐项落在区间，用于多类别联合召回。
4. 时序数据库查询：多个指标流（有序），查询最小时间窗口，所有指标流都存在采样点。

解法一：最小堆（优先队列）Python完整代码 + 逐行详细注释

importheapqclassSolution:defsmallestRange(self,nums):""" :param nums: 二维数组，k个升序子列表 :return: list[L,R]，满足条件的最小区间 """# 获取一共有多少个列表 kk=len(nums)# 小顶堆，堆内每个元素：(当前值，列表编号，该元素在子列表的索引)heap=[]# cur_max：保存当前堆中所有元素的最大值，作为候选区间右端cur_max=float('-inf')# ========= 初始化：每个子列表取第一个元素入堆 =========forlist_idxinrange(k):# 取出当前列表第0号元素val=nums[list_idx][0]# 压入堆：(数值，列表编号，元素在子数组的下标0)heapq.heappush(heap,(val,list_idx,0))# 更新当前堆的最大值ifval>cur_max:cur_max=val# 保存最终最优区间，初始设无穷大区间best_left=float('-inf')best_right=float('inf')# ========= 循环处理堆 =========whileTrue:# 弹出堆中最小元素（候选区间左边界）cur_min,list_idx,elem_idx=heapq.heappop(heap)# 【更新最优区间】# 当前候选区间 [cur_min, cur_max]# 判断：当前区间长度 比 保存的最优区间更小，就替换if(cur_max-cur_min)<(best_right-best_left):best_left=cur_min best_right=cur_max# 长度相等，左端点更小则更新（题目规则）elif(cur_max-cur_min)==(best_right-best_left):ifcur_min<best_left:best_left=cur_min best_right=cur_max# 查看这个被弹出元素，它所在的子列表还有没有下一个元素# elem_idx 是当前元素在子列表下标，下一个是 elem_idx+1next_elem_index=elem_idx+1# 如果已经走到该列表末尾，没有下一个元素，终止循环！ifnext_elem_index>=len(nums[list_idx]):break# 取出同列表下一个更大的元素next_val=nums[list_idx][next_elem_index]# 把新元素压入堆heapq.heappush(heap,(next_val,list_idx,next_elem_index))# 更新堆最大值：新元素有可能比旧cur_max大ifnext_val>cur_max:cur_max=next_val# 循环结束，返回找到的最小区间return[best_left,best_right]# 测试样例if__name__=="__main__":sol=Solution()test1=[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]print(sol.smallestRange(test1))# [20, 24]test2=[[1,2,3],[1,2,3],[1,2,3]]print(sol.smallestRange(test2))# [1, 1]

解法二：合并数组+滑动窗口（最小覆盖窗口）Python完整代码+逐行注释

fromcollectionsimportdefaultdictclassSolution2:defsmallestRange(self,nums):# k是子列表总个数k=len(nums)# all_pairs: 存储 (数值，所属列表编号)all_pairs=[]# 遍历每一个子列表，把元素打包，存入all_pairsforlist_id,sublistinenumerate(nums):fornuminsublist:all_pairs.append((num,list_id))# 将全部元素按数值从小到大排序all_pairs.sort()# 哈希表：key=列表编号，value=当前窗口里面该列表出现多少次count_dict=defaultdict(int)# cover：当前窗口覆盖了多少个不同列表，目标cover == kcover=0# 滑动窗口左指针left=0# 保存最优区间bestL=float('-inf')bestR=float('inf')# right为右指针，遍历全部排序后的元素forrightinrange(len(all_pairs)):val,list_id=all_pairs[right]count_dict[list_id]+=1# 如果这个列表之前窗口里没有，覆盖数量+1ifcount_dict[list_id]==1:cover+=1# 窗口已经覆盖全部k个列表，尝试收缩左边界，找更小区间whilecover==k:curr_val_left,curr_listid_left=all_pairs[left]currL=curr_val_left currR=val# 更新最优区间if(currR-currL)<(bestR-bestL):bestL=currL bestR=currRelif(currR-currL)==(bestR-bestL):ifcurrL<bestL:bestL=currL bestR=currR# 左指针右移，窗口缩小count_dict[curr_listid_left]-=1# 如果这个列表在窗口中清零，覆盖数减少，退出while循环ifcount_dict[curr_listid_left]==0:cover-=1left+=1return[bestL,bestR]# 测试if__name__=="__main__":sol2=Solution2()test1=[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]print(sol2.smallestRange(test1))# [20, 24]

两种方案对比

面试常问坑点

1. 区间长度相同，优先左端点更小；不要忘记这个判断。
2. 堆里面必须记录所属列表编号和下标，不然不知道取出元素来自哪个数组、取哪个下一个值。
3. 堆算法只要一个子列表耗尽，立刻退出，不能继续循环。
4. 元素可以是负数，初始化区间要用无穷，不能初始化为0。