难度: Hard
你有 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]
提示：
nums.length == k1 <= k <= 35001 <= nums[i].length <= 50-105 <= nums[i][j] <= 105nums[i] 按非递减顺序排列运行时间: 107 ms
内存: 23.4 MB
class Solution:
def smallestRange(self, A: List[List[int]]) -> List[int]:
groups = len(A)
# 每个数字绑定组号, 排序后滑窗, 找到最短满足窗体包含所有组
B = [(x, i) for i, v in enumerate(A) for x in v]
B.sort()
ans = [-inf, inf]
mp = Counter()
l = 0
for _, (y, y_group) in enumerate(B):
mp[y_group] += 1
while len(mp) == groups:
x, x_group = B[l][0], B[l][1]
diff = y - x - (ans[1] - ans[0])
if diff < 0 or (diff == 0 and y < ans[0]):
ans = [x, y]
mp[x_group] -= 1
if not mp[x_group]:
del mp[x_group]
l += 1
return ans
该题解的思路是先将每个数字与其所在的组号绑定在一起,形成(数字,组号)的元组,然后对这些元组进行排序。接着使用滑动窗口的方法,通过左右指针维护一个窗口,保证窗口内包含了所有的组。在滑动窗口的过程中,记录下窗口大小最小的区间作为答案。具体实现时,使用哈希表 mp 来统计当前窗口内每个组出现的次数,当 mp 的大小等于总组数时,说明当前窗口已经包含了所有的组,此时更新最小区间,并尝试通过收缩左边界来缩小区间大小。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def smallestRange(self, A: List[List[int]]) -> List[int]:
groups = len(A)
# 每个数字绑定组号, 排序后滑窗, 找到最短满足窗体包含所有组
B = [(x, i) for i, v in enumerate(A) for x in v]
B.sort()
ans = [-inf, inf]
mp = Counter()
l = 0
for _, (y, y_group) in enumerate(B):
mp[y_group] += 1
while len(mp) == groups:
x, x_group = B[l][0], B[l][1]
diff = y - x - (ans[1] - ans[0])
if diff < 0 or (diff == 0 and y < ans[0]):
ans = [x, y]
mp[x_group] -= 1
if not mp[x_group]:
del mp[x_group]
l += 1
return ans
在该算法中，初始化哈希表`mp`并不需要预先包含所有组号。哈希表`mp`用于动态追踪窗口内每个组的元素计数。只有当某个组的元素首次出现在窗口中时，该组号才会被加入到`mp`中，并开始计数。这种动态添加的方式可以有效地处理并记录各个组的元素状态，而不需要在初始化时就包含所有组号。
当一个或多个子列表为空时，这个算法不会有效，因为这意味着某些组没有任何元素，从而无法形成一个完整覆盖所有组的窗口。为了处理这种情况，可以在算法开始之前添加一个检查，确保所有输入的子列表都是非空的。如果发现任何一个列表为空，则可以直接返回一个错误信息或特定的输出，表明不可能找到一个包含所有组的区间。
对元组`(数字, 组号)`进行排序是为了让所有来自不同组的数字按从小到大的顺序排列，这样可以更容易地通过滑动窗口来找到包含所有组的最小区间。如果直接在原始列表上滑动，由于每个列表的数字可能是无序的，且不同列表之间的数字无法有效比较，将难以实现有效的窗口滑动来覆盖所有组。排序后，可以确保窗口内的数字是连续的，并且每次扩展或收缩窗口都是有序进行，这对于追踪当前最小区间尤为重要。
在滑动窗口中，左指针`l`的移动是为了尝试缩小当前区间的大小，同时保持窗口内包含所有组。当哈希表`mp`中某个组的计数变为0时，意味着该组的元素已经完全不在当前窗口内，因此需要移动左指针来寻找一个新的可能的最小区间，这可能涉及将左指针移动到新的位置以重新包含丢失的组。这种操作通常不会错过潜在的最小区间，因为一旦某个组元素完全不在窗口内，当前的窗口已经不再有效，必须调整窗口以重新满足条件。