一点题外话
上次在我的公众号给大家做了一个小调查《投出你想要的题解编程语言吧~》。以下是调查的结果：
投票结果
而关于其他，则大多数是 Go 语言。
投其他的人都写了什么？
由于 Java 和 Python 所占比例已经超过了 60%，这次我尝试一下 Java 和 Python 双语言来写，感谢 @CaptainZ 提供的 Java 代码。同时为了「不让文章又臭又长，我将 Java 本文所有代码（Java 和 Python）都放到了力扣加加官网上」，网站地址：https://leetcode-solution.cn/solution-code
?
如果不科学上网的话，可能打开会很慢。
?
正文
大家好，我是 lucifer。今天给大家带来的是《堆》专题。先上下本文的提纲，这个是我用 mindmap 画的一个脑图，之后我会继续完善，将其他专题逐步完善起来。
?
大家也可以使用 vscode blink-mind 打开源文件查看，里面有一些笔记可以点开查看。源文件可以去我的公众号《力扣加加》回复脑图获取，以后脑图也会持续更新更多内容。vscode 插件地址：https://marketplace.visualstudio.com/items?itemName=awehook.vscode-blink-mind
?
本系列包含以下专题：
本次是下篇，没有看过上篇的同学强烈建议先阅读上篇几乎刷完了力扣所有的堆题，我发现了这些东西。。。(第一弹)
这是第二部分，后面的内容更加干货，分别是「三个技巧」和「四大应用」。这两个主题是专门教你怎么解题的。掌握了它，力扣中的大多数堆的题目都不在话下（当然我指的仅仅是题目中涉及到堆的部分）。
警告： 本章的题目基本都是力扣 hard 难度，这是因为堆的题目很多标记难度都不小，关于这点在前面也介绍过了。
一点说明
在上主菜之前，先给大家来个开胃菜。
这里给大家介绍两个概念，分别是「元组」和「模拟大顶堆」 。之所以进行这些说明就是防止大家后面看不懂。
元组
使用堆不仅仅可以存储单一值，比如 [1,2,3,4] 的 1，2，3，4 分别都是单一值。除了单一值，也可以存储复合值，比如对象或者元组等。
这里我们介绍一种存储元组的方式，这个技巧会在后面被广泛使用，请务必掌握。比如 [(1,2,3), (4,5,6), (2,1,3),(4,2,8)]。
h = [(1,2,3), (4,5,6), (2,1,3),(4,2,8)]
heapq.heappify(h) # 堆化（小顶堆）
heapq.heappop() # 弹出 (1,2,3)
heapq.heappop() # 弹出 (2,1,3)
heapq.heappop() # 弹出 (4,2,8)
heapq.heappop() # 弹出 (4,5,6)
用图来表示堆结构就是下面这样：
使用元组的小顶堆
简单解释一下上面代码的执行结果。
使用元组的方式，默认将元组第一个值当做键来比较。如果第一个相同，继续比较第二个。比如上面的 (4,5,6) 和 (4,2,8)，由于第一个值相同，因此继续比较后一个，又由于 5 比 2 大，因此 (4,2,8)先出堆。
使用这个技巧有两个作用：
- 携带一些额外的信息。 比如我想求二维矩阵中第 k 小数，当然是以值作为键。但是处理过程又需要用到其行和列信息，那么使用元组就很合适，比如 (val, row, col)这样的形式。
- 想根据两个键进行排序，一个主键一个副键。这里面又有两种典型的用法， 2.1 一种是两个都是同样的顺序，比如都是顺序或者都是逆序。 2.2 另一种是两个不同顺序排序，即一个是逆序一个是顺序。
由于篇幅原因，具体就不再这里展开了，大家在平时做题过程中留意可以一下，有机会我会单独开一篇文章讲解。
?
如果你所使用的编程语言没有堆或者堆的实现不支持元组，那么也可以通过简单的改造使其支持，主要就是自定义比较逻辑即可。
?
模拟大顶堆
由于 Python 没有大顶堆。因此我这里使用了小顶堆进行模拟实现。即将原有的数全部取相反数，比如原数字是 5，就将 -5 入堆。经过这样的处理，小顶堆就可以当成大顶堆用了。不过需要注意的是，当你 pop 出来的时候， 「记得也要取反，将其还原回来」哦。
代码示例：
h = []
A = [1,2,3,4,5]
for a in A:
heapq.heappush(h, -a)
-1 * heapq.heappop(h) # 5
-1 * heapq.heappop(h) # 4
-1 * heapq.heappop(h) # 3
-1 * heapq.heappop(h) # 2
-1 * heapq.heappop(h) # 1
用图来表示就是下面这样：
小顶堆模拟大顶堆
铺垫就到这里，接下来进入正题。
三个技巧
技巧一 - 固定堆
这个技巧指的是固定堆的大小 k 不变，代码上可通过「每 pop 出去一个就 push 进来一个」来实现。而由于初始堆可能是 0，我们刚开始需要一个一个 push 进堆以达到堆的大小为 k，因此严格来说应该是「维持堆的大小不大于 k」。
固定堆一个典型的应用就是求第 k 小的数。其实求第 k 小的数最简单的思路是建立小顶堆，将所有的数「先全部入堆，然后逐个出堆，一共出堆 k 次」。最后一次出堆的就是第 k 小的数。
然而，我们也可不先全部入堆，而是建立「大顶堆」（注意不是上面的小顶堆），并维持堆的大小为 k 个。如果新的数入堆之后堆的大小大于 k，则需要将堆顶的数和新的数进行比较，「并将较大的移除」。这样可以保证「堆中的数是全体数字中最小的 k 个」，而这最小的 k 个中最大的（即堆顶）不就是第 k 小的么？这也就是选择建立大顶堆，而不是小顶堆的原因。
固定大顶堆求第 5 小的数
简单一句话总结就是「固定一个大小为 k 的大顶堆可以快速求第 k 小的数，反之固定一个大小为 k 的小顶堆可以快速求第 k 大的数」。比如力扣 2020-02-24 的周赛第三题5663. 找出第 K 大的异或坐标值[1]就可以用固定小顶堆技巧来实现（这道题让你求第 k 大的数）。
这么说可能你的感受并不强烈，接下来我给大家举两个例子来帮助大家加深印象。
295. 数据流的中位数
题目描述
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
进阶:
如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
思路
这道题实际上可看出是求第 k 小的数的特例了。
因此我们的可以维护两个固定堆，固定堆的大小为 和 ，也就是两个堆的大小「最多」相差 1，更具体的就是 。
基于上面提到的知识，我们可以：
有了这样一个知识，剩下的只是如何维护两个堆的大小了。
至此，可能你已经明白了为什么分别建立两个堆，并且需要一个大顶堆一个小顶堆。这其中的原因正如上面所描述的那样。
固定堆的应用常见还不止于此，我们继续看一道题。
代码
class MedianFinder:
def __init__(self):
self.min_heap = []
self.max_heap = []
def addNum(self, num: int) -> None:
if not self.max_heap or num < -self.max_heap[0]:
heapq.heappush(self.max_heap, -num)
else:
heapq.heappush(self.min_heap, num)
if len(self.max_heap) > len(self.min_heap) + 1:
heappush(self.min_heap, -heappop(self.max_heap))
elif len(self.min_heap) > len(self.max_heap):
heappush(self.max_heap, -heappop(self.min_heap))
def findMedian(self) -> float:
if len(self.min_heap) == len(self.max_heap): return (self.min_heap[0] - self.max_heap[0]) / 2
return -self.max_heap[0]
(代码 1.3.1)
857. 雇佣 K 名工人的最低成本
题目描述
有 N 名工人。 第 i 名工人的工作质量为 quality[i] ，其最低期望工资为 wage[i] 。
现在我们想雇佣 K 名工人组成一个工资组。在雇佣 一组 K 名工人时，我们必须按照下述规则向他们支付工资：
对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。
返回组成一个满足上述条件的工资组至少需要多少钱。
示例 1：
输入： quality = [10,20,5], wage = [70,50,30], K = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。
示例 2：
输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。
提示：
1 <= K <= N <= 10000，其中 N = quality.length = wage.length
1 <= quality[i] <= 10000
1 <= wage[i] <= 10000
与正确答案误差在 10^-5 之内的答案将被视为正确的。
思路
题目要求我们选择 k 个人，按其工作质量与同组其他工人的工作质量的比例来支付工资，并且工资组中的每名工人至少应当得到他们的最低期望工资。
换句话说，同一组的 k 个人他们的工作质量和工资比是一个固定值才能使支付的工资最少。请先理解这句话，后面的内容都是基于这个前提产生的。
我们不妨定一个指标「工作效率」，其值等于 q / w。前面说了这 k 个人的 q / w 是相同的才能保证工资最少，并且这个 q / w 一定是这 k 个人最低的（短板），否则一定会有人得不到最低期望工资。
于是我们可以写出下面的代码：
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
eff = [(q / w, q, w) for a, b in zip(quality, wage)]
eff.sort(key=lambda a: -a[0])
ans = float('inf')
for i in range(K-1, len(eff)):
h = []
k = K - 1
rate, _, total = eff[i]
# 找出工作效率比它高的 k 个人，这 k 个人的工资尽可能低。
# 由于已经工作效率倒序排了，因此前面的都是比它高的，然后使用堆就可得到 k 个工资最低的。
for j in range(i):
heapq.heappush(h, eff[j][1] / rate)
while k > 0:
total += heapq.heappop(h)
k -= 1
ans = min(ans, total)
return ans
(代码 1.3.2)
这种做法每次都 push 很多数，并 pop k 次，并没有很好地利用堆的「动态」特性，而只利用了其「求极值」的特性。
一个更好的做法是使用「固定堆技巧」。
这道题可以换个角度思考。其实这道题不就是让我们选 k 个人，工作效率比取他们中最低的，并按照这个最低的工作效率计算总工资，找出最低的总工资么？ 因此这道题可以固定一个大小为 k 的大顶堆，通过一定操作保证堆顶的就是第 k 小的（操作和前面的题类似）。
并且前面的解法中堆使用了三元组 (q / w, q, w)，实际上这也没有必要。因为已知其中两个，可推导出另外一个，因此存储两个就行了，而又由于我们需要「根据工作效率比做堆的键」，因此任意选一个 q 或者 w 即可，这里我选择了 q，即存 (q/2, q) 二元组。
具体来说就是：以 rate 为最低工作效率比的 k 个人的总工资 = ，这里的 rate 就是当前的 q / w，同时也是 k 个人的 q / w 的最小值。
代码
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
effs = [(q / w, q) for q, w in zip(quality, wage)]
effs.sort(key=lambda a: -a[0])
ans = float('inf')
h = []
total = 0
for rate, q in effs:
heapq.heappush(h, -q)
total += q
if len(h) > K:
total += heapq.heappop(h)
if len(h) == K:
ans = min(ans, total / rate)
return ans
(代码 1.3.3)
技巧二 - 多路归并
这个技巧其实在前面讲「超级丑数」的时候已经提到了，只是没有给这种类型的题目一个「名字」。
其实这个技巧，叫做多指针优化可能会更合适，只不过这个名字实在太过朴素且容易和双指针什么的混淆，因此我给 ta 起了个别致的名字 - 「多路归并」。
这样描述比较抽象，接下来通过几个例子来加深一下大家的理解。
这里我给大家精心准备了「四道难度为 hard」 的题目。 掌握了这个套路就可以去快乐地 AC 这四道题啦。
1439. 有序矩阵中的第 k 个最小数组和
题目描述
给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
示例 1：
输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。
示例 2：
输入：mat = [[1,3,11],[2,4,6]], k = 9
输出：17
示例 3：
输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。
示例 4：
输入：mat = [[1,1,10],[2,2,9]], k = 7
输出：12
提示：
m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组
思路
其实这道题就是给你 m 个长度均相同的一维数组，让我们从这 m 个数组中分别选出一个数，即一共选取 m 个数，求这 m 个数的和是「所有选取可能性」中和第 k 小的。
一个朴素的想法是使用多指针来解。对于这道题来说就是使用 m 个指针，分别指向 m 个一维数组，指针的位置表示当前选取的是该一维数组中第几个。
以题目中的 mat = [[1,3,11],[2,4,6]], k = 5 为例。
到这里已经分叉了，出现了两种情况(注意看粗体的位置，粗体表示的是指针的位置)：
- [1,「3」,11],[「2」,4,6] 和为 5
- [「1」,3,11],[2,「4」,6] 和为 5
接下来，这两种情况应该「齐头并进，共同进行下去」。
对于情况 1 来说，接下来移动又有两种情况。
- [1,3,「11」],[「2」,4,6] 和为 13
- [1,「3」,11],[2,「4」,6] 和为 7
对于情况 2 来说，接下来移动也有两种情况。
- [1,「3」,11],[2,「4」,6] 和为 7
- [「1」,3,11],[2,4,「6」] 和为 7
我们通过比较这四种情况，得出结论： 第 4，5，6 小的数都是 7。但第 7 小的数并不一定是 13。原因和上面类似，可能第 7 小的就隐藏在前面的 7 分裂之后的新情况中，实际上确实如此。因此我们需要继续执行上述逻辑。
进一步，我们可以将上面的思路拓展到一般情况。
上面提到了题目需要求的其实是第 k 小的和，而最小的我们是容易知道的，即所有的一维数组首项和。我们又发现，根据最小的，我们可以推导出第 2 小，推导的方式就是移动其中一个指针，这就一共分裂出了 n 种情况了，其中 n 为一维数组长度，第 2 小的就在这分裂中的 n 种情况中，而筛选的方式是这 n 种情况和「最小」的，后面的情况也是类似。不难看出每次分裂之后极值也发生了变化，因此这是一个明显的求动态求极值的信号，使用堆是一个不错的选择。
那代码该如何书写呢？
上面说了，我们先要初始化 m 个指针，并赋值为 0。对应伪代码：
# 初始化堆
h = []
# sum(vec[0] for vec in mat) 是 m 个一维数组的首项和
# [0] * m 就是初始化了一个长度为 m 且全部填充为 0 的数组。
# 我们将上面的两个信息组装成元祖 cur 方便使用
cur = (sum(vec[0] for vec in mat), [0] * m)
# 将其入堆
heapq.heappush(h, cur)
接下来，我们每次都移动一个指针，从而形成分叉出一条新的分支。每次从堆中弹出一个最小的，弹出 k 次就是第 k 小的了。伪代码：
for 1 to K:
# acc 当前的和， pointers 是指针情况。
acc, pointers = heapq.heappop(h)
# 每次都粗暴地移动指针数组中的一个指针。每移动一个指针就分叉一次， 一共可能移动的情况是 n，其中 n 为一维数组的长度。
for i, pointer in enumerate(pointers):
# 如果 pointer == len(mat[0]) - 1 说明到头了，不能移动了
if pointer != len(mat[0]) - 1:
# 下面两句话的含义是修改 pointers[i] 的指针 为 pointers[i] + 1
new_pointers = pointers.copy()
new_pointers[i] += 1
# 将更新后的 acc 和指针数组重新入堆
heapq.heappush(h, (acc + mat[i][pointer + 1] - mat[i][pointer], new_pointers))
这是「多路归并」问题的核心代码，请务必记住。
?
代码看起来很多，其实去掉注释一共才七行而已。
?
上面的伪代码有一个问题。比如有两个一维数组，指针都初始化为 0。第一次移动第一个一维数组的指针，第二次移动第二个数组的指针，此时指针数组为 [1, 1]，即全部指针均指向下标为 1 的元素。而如果第一次移动第二个一维数组的指针，第二次移动第一个数组的指针，此时指针数组仍然为 [1, 1]。这实际上是一种情况，如果不加控制会被计算两次导致出错。
一个可能的解决方案是使用 hashset 记录所有的指针情况，这样就避免了同样的指针被计算多次的问题。为了做到这一点，我们需要对指针数组的使用做一些微调，即使用元组代替数组。原因在于数组是无法直接哈希化的。具体内容请参考代码区。
「多路归并」的题目，思路和代码都比较类似。为了后面的题目能够更高地理解，请务必搞定这道题，后面我们将不会这么详细地进行分析。
代码
class Solution:
def kthSmallest(self, mat, k: int) -> int:
h = []
cur = (sum(vec[0] for vec in mat), tuple([0] * len(mat)))
heapq.heappush(h, cur)
seen = set(cur)
for _ in range(k):
acc, pointers = heapq.heappop(h)
for i, pointer in enumerate(pointers):
if pointer != len(mat[0]) - 1:
t = list(pointers)
t[i] = pointer + 1
tt = tuple(t)
if tt not in seen:
seen.add(tt)
heapq.heappush(h, (acc + mat[i][pointer + 1] - mat[i][pointer], tt))
return acc
(代码 1.3.4)
719. 找出第 k 小的距离对
题目描述
给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
示例 1:
输入：
nums = [1,3,1]
k = 1
输出：0
解释：
所有数对如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
提示:
2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.
思路
不难看出所有的数对可能共 个，也就是 。
因此我们可以使用两次循环找出所有的数对，并升序排序，之后取第 k 个。
实际上，我们可使用固定堆技巧，维护一个大小为 k 的大顶堆，这样堆顶的元素就是第 k 小的，这在前面的固定堆中已经讲过，不再赘述。
class Solution:
def smallestDistancePair(self, nums: List[int], k: int) -> int:
h = []
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
a, b = nums[i], nums[j]
# 维持堆大小不超过 k
if len(h) == k and -abs(a - b) > h[0]:
heapq.heappop(h)
if len(h) < k:
heapq.heappush(h, -abs(a - b))
return -h[0]
(代码 1.3.5)
不过这种优化意义不大，因为算法的瓶颈在于 部分的枚举，我们应当设法优化这一点。
如果我们将数对进行排序，那么最小的数对距离一定在 nums[i] - nums[i - 1] 中，其中 i 为从 1 到 n 的整数，究竟是哪个取决于谁更小。接下来就可以使用上面多路归并的思路来解决了。
如果 nums[i] - nums[i - 1] 的差是最小的，那么第 2 小的一定是剩下的 n - 1 种情况和 nums[i] - nums[i - 1] 分裂的新情况。关于如何分裂，和上面类似，我们只需要移动其中 i 的指针为 i + 1 即可。这里的指针数组长度固定为 2，而不是上面题目中的 m。这里我将两个指针分别命名为 fr 和 to，分别代表 from 和 to。
代码
class Solution(object):
def smallestDistancePair(self, nums, k):
nums.sort()
# n 种候选答案
h = [(nums[i+1] - nums[i], i, i+1) for i in range(len(nums) - 1)]
heapq.heapify(h)
for _ in range(k):
diff, fr, to = heapq.heappop(h)
if to + 1 < len(nums):
heapq.heappush((nums[to + 1] - nums[fr], fr, to + 1))
return diff
(代码 1.3.6)
由于时间复杂度和 k 有关，而 k 最多可能达到 的量级，因此此方法实际上也会超时。「不过这证明了这种思路的正确性，如果题目稍加改变说不定就能用上」。
这道题可通过二分法来解决，由于和堆主题有偏差，因此这里简单讲一下。
求第 k 小的数比较容易想到的就是堆和二分法。二分的原因在于求第 k 小，本质就是求不大于其本身的有 k - 1 个的那个数。而这个问题很多时候满足单调性，因此就可使用二分来解决。
以这道题来说，最大的数对差就是数组的最大值 - 最小值，不妨记为 max_diff。我们可以这样发问：
而我们知道，发问的答案也是不严格递减的，因此使用二分就应该被想到。我们不断发问直到问到「小于 x 的有 k - 1 个」即可。然而这样的发问也有问题。原因有两个：
- 小于 x 的有 k - 1 个的数可能不止一个
- 我们无法确定小于 x 的有 k - 1 个的数一定存在。 比如数对差分别为 [1,1,1,1,2]，让你求第 3 大的，那么小于 x 有两个的数根本就不存在。
我们的思路可调整为求「小于等于 x」 有 k 个的，接下来我们使用二分法的最左模板即可解决。关于最左模板可参考我的二分查找专题
代码：
class Solution:
def smallestDistancePair(self, A: List[int], K: int) -> int:
A.sort()
l, r = 0, A[-1] - A[0]
def count_ngt(mid):
slow = 0
ans = 0
for fast in range(len(A)):
while A[fast] - A[slow] > mid:
slow += 1
ans += fast - slow
return ans
while l <= r:
mid = (l + r) // 2
if count_ngt(mid) >= K:
r = mid - 1
else:
l = mid + 1
return l
(代码 1.3.7)
632. 最小区间
题目描述
你有 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
-105 <= nums[i][j] <= 105
nums[i] 按非递减顺序排列
思路
这道题本质上就是「在 m 个一维数组中各取出一个数字，重新组成新的数组 A，使得新的数组 A 中最大值和最小值的差值（diff）最小」。
这道题和上面的题目有点类似，又略有不同。这道题是一个矩阵，上面一道题是一维数组。不过我们可以将二维矩阵看出一维数组，这样我们就可以沿用上面的思路了。
上面的思路 diff 最小的一定产生于排序之后相邻的元素之间。而这道题我们无法直接对二维数组进行排序，而且即使进行排序，也不好确定排序的原则。
我们其实可以继续使用前面两道题的思路。具体来说就是使用「小顶堆获取堆中最小值」，进而通过「一个变量记录堆中的最大值」，这样就知道了 diff，每次更新指针都会产生一个新的 diff，不断重复这个过程并维护全局最小 diff 即可。
这种算法的成立的前提是 k 个列表都是升序排列的，这里需要数组升序原理和上面题目是一样的，有序之后就可以对每个列表维护一个指针，进而使用上面的思路解决。
以题目中的 nums = [[1,2,3],[1,2,3],[1,2,3]] 为例：
我们先选取所有行的最小值，也就是 [1,1,1]，这时的 diff 为 0，全局最大值为 1，最小值也为 1。接下来，继续寻找备胎，看有没有更好的备胎供我们选择。
接下来的备胎可能产生于情况 1：
或者情况 2：
。。。
这几种情况又继续分裂更多的情况，这个就和上面的题目一样了，不再赘述。
代码
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])
(代码 1.3.8)
1675. 数组的最小偏移量
题目描述
给你一个由 n 个正整数组成的数组 nums 。
你可以对数组的任意元素执行任意次数的两类操作：
如果元素是 偶数 ，除以 2
例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]
如果元素是 奇数 ，乘上 2
例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]
数组的 偏移量 是数组中任意两个元素之间的 最大差值 。
返回数组在执行某些操作之后可以拥有的 最小偏移量 。
示例 1：
输入：nums = [1,2,3,4]
输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1
示例 2：
输入：nums = [4,1,5,20,3]
输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3
示例 3：
输入：nums = [2,10,8]
输出：3
提示：
n == nums.length
2 <= n <= 105
1 <= nums[i] <= 109
思路
题目说可对数组中每一项都执行任意次操作，但其实操作是有限的。
以题目中的 [1,2,3,4] 来说。我们可以：
用图来表示就是下面这样的：
一维数组转二维数组
这不就相当于: 从 [[1,2], [1,2], [3,6], [1,2,4]] 这样的一个二维数组中的每一行分别选取一个数，并使得其差最小么？这难道不是和上面的题目一模一样么？
这里我直接将上面的题目解法封装成了一个 api 调用了，具体看代码。
代码
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])
def minimumDeviation(self, nums: List[int]) -> int:
matrix = [[] for _ in range(len(nums))]
for i, num in enumerate(nums):
if num & 1 == 1:
matrix[i] += [num, num * 2]
else:
temp = []
while num and num & 1 == 0:
temp += [num]
num //= 2
temp += [num]
matrix[i] += temp[::-1]
a, b = self.smallestRange(matrix)
return b - a
(代码 1.3.9)