类型：字符串
-
- 最小区间 ❤️ ⭐
https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/
❓ 你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
💡 贪心 + 堆
参见：力扣加加
该问题可以转化为，从 k 个列表中各取一个数，使得这 k 个数中的最大值与最小值的差（diff）最小。
思路是我们使用多指针进行遍历，将指向的元素存入小顶堆。通过堆顶获取最小值，通过一个变量来记录最大值，这样我们可以很快地计算出 diff。每次更新指针都会产生一个新的 diff，不断重复这个过程并维护全局最小 diff 即可。
我们有这么多个指针，应该先移动哪一个呢？应该移动指向元素最小的指针（即堆顶），这样保证最小的元素被移出堆，才能保证 diff 的变化是渐进性的，才不会漏掉。
class Solution: def smallestRange(self, martrix: List[List[int]]) -> List[int]: l, r = -10**9, 10**9 # 将每一行最小的都放到堆中，同时记录其所在的行号和列号，一共 n 个齐头并进 h = [(row[0], i, 0) for i, row in enumerate(martrix)] heapq.heapify(h) # 维护最大值 max_v = max(row[0] for row in martrix) while True: min_v, row, col = heapq.heappop(h) # max_v - min_v 是当前的最大最小差值， r - l 为全局的最大最小差值。因为如果当前的更小，我们就更新全局结果 if max_v - min_v < r - l: l, r = min_v, max_v if col == len(martrix[row]) - 1: return [l, r] # 更新指针，继续往后移动一位 heapq.heappush(h, (martrix[row][col + 1], row, col + 1)) max_v = max(max_v, martrix[row][col + 1])