632 最小区（多路归并）

左手的ㄟ右手 2022-09-02 03:52 134阅读 0赞

**1. 问题描述：**

你有 k 个非递减排列的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 \[a,b\] 比 \[c,d\] 小。

**示例 1：**

输入：nums = \[\[4,10,15,24,26\], \[0,9,12,20\], \[5,18,22,30\]\]  
输出：\[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\] 中。

**示例 2：**

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

**示例 3：**

输入：nums = \[\[10,10\],\[11,11\]\]  
输出：\[10,11\]

**示例 4：**

输入：nums = \[\[10\],\[11\]\]  
输出：\[10,11\]

**示例 5：**

输入：nums = \[\[1\],\[2\],\[3\],\[4\],\[5\],\[6\],\[7\]\]  
输出：\[1,7\]  
提示：  
nums.length == k  
1 <= k <= 3500  
1 <= nums\[i\].length <= 50  
\-10 ^ 5 <= nums\[i\]\[j\] <= 10 ^ 5  
nums\[i\] 按非递减顺序排列  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists

**2. 思路分析：**

这道题目经典的做法是**多路归并**。首先题目要求我们找出一个长度最短的区间使得区间能够至少覆盖每个序列中一个数字，其实我们转变一下思路，将当前问题转化为对应的等价问题，可以发现我们相当于是在当前的序列中挑出一个最小的数n，然后在其余的每一个序列中挑选出一个大于等于n的最小的那个数这样这样每个序列中可以覆盖至少一个数，在这些序列中挑出来的数字中选出最大的那个数字表示区间的右端点，这样当前选出来的两个数就是可以覆盖所有序列中至少一个数字。对于每一个序列我们都可以找到最小值，这样在多路归并的过程中我们就可以将所有的答案枚举出来。多路归并一般是先加入每一个序列中的第一个元素，并且需要借助于一个堆来实现，由题目可知，我们需要维护的**小根堆**，这样堆顶存储的就是当前序列的最小的元素，小根堆需要维护三个信息，第一个信息是当前的数组元素值，第二个信息是当前的元素位于第几行，第三个信息是当前到的元素位于第几列，第二、三个信息就是当前元素的位置信息。堆顶可以维护所有序列中当前最小的元素，也即区间的左端点，如何维护区间的右端点呢？可以发现我们在往堆中加入元素的时候可以维护一个最大值，我们可以在往堆中加入元素的时候维护一个最大值表示我们维护的是每一个序列中大于等于当前最小值的元素中最大的那个这样就可以覆盖所有序列中至少一个数了，堆中的最大值对应的就是区间右端点的值。在枚举的时候我们每一次求解一个区间来覆盖所有序列中至少一个数字，这样就可以将可能的答案枚举出来，当我们发现某个序列中没有元素的时候我们就可以直接break，因为这个时候当前序列已经没有元素了，也即无法求解出一个区间至少覆盖区间中的一个数了。

**3. 代码如下：**

from typing import List
    import heapq
    
    
    class Solution:
        def smallestRange(self, nums: List[List[int]]) -> List[int]:
            heap = list()
            # 使用一个int类型的变量来维护当前堆中大于等于堆顶的下一个元素
            maxv = -10 ** 6
            for i in range(len(nums)):
                # 小根堆中需要维护三个信息, 第一个当前元素值, 第二个是位于第几行, 第三个是位于第几列
                heapq.heappush(heap, (nums[i][0], i, 0))
                # maxv维护区间右端点
                maxv = max(maxv, nums[i][0])
            res = list()
            # 当堆非空的时候执行循环
            while heap:
                t = heapq.heappop(heap)
                l, r = t[0], maxv
                if not res or res[1] - res[0] > r - l:
                    res = [l, r]
                # 加入下一个元素
                i, j = t[1], t[2] + 1
                # 当这一类不满足条件的时候直接break因为当前区间没有任何数字可以覆盖了
                if j < len(nums[i]):
                    heapq.heappush(heap, (nums[i][j], i, j))
                    maxv = max(maxv, nums[i][j])
                else:
                    break
            return res