LeetCode 632 题目题号632 题目名称最小区间 Smallest Range Covering Elements from K ListsHard题目描述你有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]解释列表124 在区间 [20,24]列表220 在区间 [20,24]列表322 在区间 [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个元素这k个元素构成候选区间每次把k个里面最小的那个换掉取它所在数组的下一个更大的值再形成新区间不断更新最优答案。为什么这个贪心成立当前区间的短板是最小值。想要缩小区间只能把最小值变大数组升序下一个元素更大最大值只能不变或者变大。一旦某个数组没有下一个元素算法停止没法继续构造新候选区间。两种主流解法解法一最小堆优先队列【最优解法面试首选】✅ 时间复杂度 O(N logk)N是全部元素总数k是列表数量空间 O(k)思路步骤初始化每个数组拿出第一个元素放进小顶堆同时记录这k个元素里的最大值cur_max。堆里面存三元组(数值所属列表编号该元素在列表中的下标)循环① 弹出堆里最小元素cur_min此时候选区间就是[cur_min, cur_max]对比更新全局最优区间。② 看这个最小元素所在数组后面还有没有元素- 有取出下一个元素推入堆更新cur_max新元素可能更大继续循环。- 没有直接终止循环因为这个数组再也拿不出更大元素无法再凑齐k个元素构成合法区间。返回最优区间。卡点解释为什么数组用完就停我们必须保证堆里永远有每个列表恰好一个元素才能保证区间覆盖全部k个列表。一旦某列表元素耗尽再也凑不出满足条件的候选区间直接退出。解法二合并全部元素 滑动窗口双指针哈希计数✅ 时间复杂度 O(N logN)N是全部元素空间O(N)思路步骤把所有元素拆成(value, 原列表编号)拼成一个大列表按value排序。滑动窗口left、rightright不断向右扩张窗口。哈希表记录窗口内每个列表编号出现次数记录窗口覆盖了多少个不同列表cover_cnt。当cover_cnt k窗口满足条件尝试移动left缩小窗口更新最小区间直到窗口不再覆盖全部k个列表。类比LeetCode76 最小覆盖子串。把“字符”换成“列表编号”。缺点需要存储全部元素数据量大时内存更高优点堆不熟的时候容易联想最小覆盖子串。暴力解法仅理解不推荐会超时枚举从每个数组挑选一个元素的全部组合算出区间记录最小。组合爆炸k很大直接超时。应用场景举例传感器多源数据采集k个传感器每个传感器按时间采集一组有序测量值找一个最短时间窗口每个传感器至少有一条数据落在窗口内用于多传感器时间对齐。多供应商价格筛选多家供应商的产品报价有序列表找最小价格区间每家至少有一款产品在区间内采购筛选。推荐系统多个分类的有序推荐分数找分数区间每个分类至少一个推荐项落在区间用于多类别联合召回。时序数据库查询多个指标流有序查询最小时间窗口所有指标流都存在采样点。解法一最小堆优先队列Python完整代码 逐行详细注释importheapqclassSolution:defsmallestRange(self,nums): :param nums: 二维数组k个升序子列表 :return: list[L,R]满足条件的最小区间 # 获取一共有多少个列表 kklen(nums)# 小顶堆堆内每个元素(当前值列表编号该元素在子列表的索引)heap[]# cur_max保存当前堆中所有元素的最大值作为候选区间右端cur_maxfloat(-inf)# 初始化每个子列表取第一个元素入堆 forlist_idxinrange(k):# 取出当前列表第0号元素valnums[list_idx][0]# 压入堆(数值列表编号元素在子数组的下标0)heapq.heappush(heap,(val,list_idx,0))# 更新当前堆的最大值ifvalcur_max:cur_maxval# 保存最终最优区间初始设无穷大区间best_leftfloat(-inf)best_rightfloat(inf)# 循环处理堆 whileTrue:# 弹出堆中最小元素候选区间左边界cur_min,list_idx,elem_idxheapq.heappop(heap)# 【更新最优区间】# 当前候选区间 [cur_min, cur_max]# 判断当前区间长度 比 保存的最优区间更小就替换if(cur_max-cur_min)(best_right-best_left):best_leftcur_min best_rightcur_max# 长度相等左端点更小则更新题目规则elif(cur_max-cur_min)(best_right-best_left):ifcur_minbest_left:best_leftcur_min best_rightcur_max# 查看这个被弹出元素它所在的子列表还有没有下一个元素# elem_idx 是当前元素在子列表下标下一个是 elem_idx1next_elem_indexelem_idx1# 如果已经走到该列表末尾没有下一个元素终止循环ifnext_elem_indexlen(nums[list_idx]):break# 取出同列表下一个更大的元素next_valnums[list_idx][next_elem_index]# 把新元素压入堆heapq.heappush(heap,(next_val,list_idx,next_elem_index))# 更新堆最大值新元素有可能比旧cur_max大ifnext_valcur_max:cur_maxnext_val# 循环结束返回找到的最小区间return[best_left,best_right]# 测试样例if__name____main__:solSolution()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是子列表总个数klen(nums)# all_pairs: 存储 (数值所属列表编号)all_pairs[]# 遍历每一个子列表把元素打包存入all_pairsforlist_id,sublistinenumerate(nums):fornuminsublist:all_pairs.append((num,list_id))# 将全部元素按数值从小到大排序all_pairs.sort()# 哈希表key列表编号value当前窗口里面该列表出现多少次count_dictdefaultdict(int)# cover当前窗口覆盖了多少个不同列表目标cover kcover0# 滑动窗口左指针left0# 保存最优区间bestLfloat(-inf)bestRfloat(inf)# right为右指针遍历全部排序后的元素forrightinrange(len(all_pairs)):val,list_idall_pairs[right]count_dict[list_id]1# 如果这个列表之前窗口里没有覆盖数量1ifcount_dict[list_id]1:cover1# 窗口已经覆盖全部k个列表尝试收缩左边界找更小区间whilecoverk:curr_val_left,curr_listid_leftall_pairs[left]currLcurr_val_left currRval# 更新最优区间if(currR-currL)(bestR-bestL):bestLcurrL bestRcurrRelif(currR-currL)(bestR-bestL):ifcurrLbestL:bestLcurrL bestRcurrR# 左指针右移窗口缩小count_dict[curr_listid_left]-1# 如果这个列表在窗口中清零覆盖数减少退出while循环ifcount_dict[curr_listid_left]0:cover-1left1return[bestL,bestR]# 测试if__name____main__:sol2Solution2()test1[[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]print(sol2.smallestRange(test1))# [20, 24]两种方案对比方案时间复杂度空间优点缺点最小堆O(N logk)O(k)内存占用低大数据性能好推荐面试写堆操作理解门槛稍高滑动窗口O(N logN)O(N)思路可以复用最小覆盖子串全部元素排序内存消耗更大面试常问坑点区间长度相同优先左端点更小不要忘记这个判断。堆里面必须记录所属列表编号和下标不然不知道取出元素来自哪个数组、取哪个下一个值。堆算法只要一个子列表耗尽立刻退出不能继续循环。元素可以是负数初始化区间要用无穷不能初始化为0。