关于leetcode:几乎刷完了力扣所有的堆题我发现了这些东西第二弹

一点题外话

上次在我的公众号给大家做了一个小考察《投出你想要的题解编程语言吧~》。以下是考察的后果：

而对于其余，则大多数是 Go 语言。

因为 Java 和 Python 所占比例曾经超过了 60%，这次我尝试一下 Java 和 Python 双语言来写，感激 @CaptainZ 提供的 Java 代码。同时为了 不让文章又臭又长，我将 Java 本文所有代码（Java 和 Python）都放到了力扣加加官网上，网站地址：https://leetcode-solution.cn/…

如果不迷信上网的话，可能关上会很慢。

注释

大家好，我是 lucifer。明天给大家带来的是《堆》专题。先高低本文的提纲，这个是我用 mindmap 画的一个脑图，之后我会持续欠缺，将其余专题逐步完善起来。

大家也能够应用 vscode blink-mind 关上源文件查看，外面有一些笔记能够点开查看。源文件能够去我的公众号《力扣加加》回复脑图获取，当前脑图也会继续更新更多内容。vscode 插件地址：https://marketplace.visualstu…

本系列蕴含以下专题：

• 简直刷完了力扣所有的链表题，我发现了这些货色。。。
• 简直刷完了力扣所有的树题，我发现了这些货色。。。
• 简直刷完了力扣所有的堆题，我发现了这些货色。。。（第一弹）

<!– more –>

本次是下篇，没有看过上篇的同学强烈建议先浏览上篇简直刷完了力扣所有的堆题，我发现了这些货色。。。(第一弹)

这是第二局部，前面的内容更加干货，别离是 三个技巧 和四大利用。这两个主题是专门教你怎么解题的。把握了它，力扣中的大多数堆的题目都不在话下（当然我指的仅仅是题目中波及到堆的局部）。

正告：本章的题目根本都是力扣 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)先出堆。

应用这个技巧有两个作用：

1. 携带一些额定的信息。比方我想求二维矩阵中第 k 小数，当然是以值作为键。然而处理过程又须要用到其行和列信息，那么应用元组就很适合，比方 (val, row, col)这样的模式。
2. 想依据两个键进行排序，一个主键一个副键。这外面又有两种典型的用法，

   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 小的么？这也就是抉择建设大顶堆，而不是小顶堆的起因。

简略一句话总结就是 固定一个大小为 k 的大顶堆能够疾速求第 k 小的数，反之固定一个大小为 k 的小顶堆能够疾速求第 k 大的数。比方力扣 2020-02-24 的周赛第三题 5663. 找出第 K 大的异或坐标值就能够用固定小顶堆技巧来实现（这道题让你求第 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 小的数的特例了。

• 如果列表长度是奇数，那么 k 就是 (n + 1) / 2，中位数就是第 k 个数，。比方 n 是 5，k 就是 (5 + 1)/ 2 = 3。
• 如果列表长度是偶数，那么 k 就是 (n + 1) / 2 和 (n + 1) / 2 + 1，中位数则是这两个数的平均值。比方 n 是 6，k 就是 (6 + 1)/ 2 = 3 和 (6 + 1) / 2 + 1 = 4。

因而咱们的能够保护两个固定堆，固定堆的大小为 $(n + 1) \div 2$ 和 $n – (n + 1)\div2$，也就是两个堆的大小 最多 相差 1，更具体的就是 $ 0 <= (n + 1) \div 2 – (n – (n + 1) \div 2) <= 1$。

基于下面提到的常识，咱们能够：

• 建设一个大顶堆，并寄存最小的 $(n + 1) \div 2$ 个数，这样堆顶的数就是第 $(n + 1) \div 2$ 小的数，也就是奇数状况的中位数。
• 建设一个小顶堆，并寄存最大的 n – $(n + 1) \div 2$ 个数，这样堆顶的数就是第 n – $(n + 1) \div 2$ 大的数，联合下面的大顶堆，可求出偶数状况的中位数。

有了这样一个常识，剩下的只是如何保护两个堆的大小了。

• 如果大顶堆的个数比小顶堆少，那么就将小顶堆中最小的转移到大顶堆。而因为小顶堆保护的是最大的 k 个数，大顶堆保护的是最小的 k 个数，因而小顶堆堆顶肯定大于等于大顶堆堆顶，并且这两个堆顶是 此时 的中位数。
• 如果大顶堆的个数比小顶堆的个数多 2，那么就将大顶堆中最大的转移到小顶堆，理由同上。

至此，可能你曾经明确了为什么别离建设两个堆，并且须要一个大顶堆一个小顶堆。这其中的起因正如下面所形容的那样。

固定堆的利用常见还不止于此，咱们持续看一道题。

代码

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 集体的总工资 = $\displaystyle \sum_{n=1}^{k}{q}_{n}/rate$，这里的 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 起了个别致的名字 – 多路归并。

• 多路体现在：有多条候选路线。代码上，咱们可应用多指针来示意。
• 归并体现在：后果可能是多个候选路线中最长的或者最短，也可能是第 k 个 等。因而咱们须要对多条路线的后果进行比拟，并依据题目形容舍弃或者选取某一个或多个路线。

这样形容比拟形象，接下来通过几个例子来加深一下大家的了解。

这里我给大家精心筹备了 四道难度为 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 为例。

• 先初始化两个指针 p1,p2，别离指向两个一维数组的结尾，代码示意就是全副初始化为 0。
• 此时两个指针指向的数字和为 1 + 2 = 3，这就是第 1 小的和。
• 接下来，咱们挪动其中一个指针。此时咱们能够挪动 p1，也能够挪动 p2。
• 那么第 2 小的肯定是挪动 p1 和 挪动 p2 这两种状况的较小值。而这里挪动 p1 和 p2 实际上都会失去 5，也就是说第 2 和第 3 小的和都是 5。

到这里曾经分叉了，呈现了两种状况(留神看粗体的地位，粗体示意的是指针的地位)：

1. [1,3,11],[2,4,6] 和为 5
2. [1,3,11],[2,4,6] 和为 5

接下来，这两种状况应该 齐头并进，独特进行上来。

对于状况 1 来说，接下来挪动又有两种状况。

1. [1,3,11],[2,4,6] 和为 13
2. [1,3,11],[2,4,6] 和为 7

对于状况 2 来说，接下来挪动也有两种状况。

1. [1,3,11],[2,4,6] 和为 7
2. [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.

思路

不难看出所有的数对可能共 $C_n^2$ 个，也就是 $n\times(n-1)\div2$。

因而咱们能够应用两次循环找出所有的数对，并升序排序，之后取第 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)

不过这种优化意义不大，因为算法的瓶颈在于 $N^2$ 局部的枚举，咱们该当设法优化这一点。

如果咱们将数对进行排序，那么最小的数对间隔肯定在 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 最多可能达到 $N^2$ 的量级，因而此办法实际上也会超时。不过这证实了这种思路的正确性，如果题目稍加扭转说不定就能用上。

这道题可通过二分法来解决，因为和堆主题有偏差，因而这里简略讲一下。

求第 k 小的数比拟容易想到的就是堆和二分法。二分的起因在于求第 k 小，实质就是求不大于其自身的有 k – 1 个的那个数。而这个问题很多时候满足枯燥性，因而就可应用二分来解决。

以这道题来说，最大的数对差就是数组的最大值 – 最小值，无妨记为 max_diff。咱们能够这样提问：

• 数对差小于 max_diff 的有几个？
• 数对差小于 max_diff – 1 的有几个？
• 数对差小于 max_diff – 2 的有几个？
• 数对差小于 max_diff – 3 的有几个？
• 数对差小于 max_diff – 4 的有几个？
• 。。。

而咱们晓得，提问的答案也是不严格递加的，因而应用二分就应该被想到。咱们一直提问直到问到 小于 x 的有 k – 1 个 即可。然而这样的提问也有问题。起因有两个：

1. 小于 x 的有 k – 1 个的数可能不止一个
2. 咱们无奈确定小于 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,2,3]
• [1,2,3]
• [1,2,3]

咱们先选取所有行的最小值，也就是 [1,1,1]，这时的 diff 为 0，全局最大值为 1，最小值也为 1。接下来，持续寻找备胎，看有没有更好的备胎供咱们抉择。

接下来的备胎可能产生于状况 1：

• [1,2,3]
• [1,2,3]
• [1,2,3] 挪动了这行的指针，将其从原来的 0 挪动一个单位达到 1。

或者状况 2：

• [1,2,3]
• [1,2,3]挪动了这行的指针，将其从原来的 0 挪动一个单位达到 1。
• [1,2,3]

。。。

这几种状况又持续决裂更多的状况，这个就和下面的题目一样了，不再赘述。

代码

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

思路

题目说可对数组中每一项都执行任意次操作，但其实操作是无限的。

• 咱们只能对奇数进行一次 2 倍操作，因为 2 倍之后其就变成了偶数了。
• 咱们能够对偶数进行若干次除 2 操作，直到等于一个奇数，不难看出这也是一个无限次的操作。

以题目中的 [1,2,3,4] 来说。咱们能够：

• 将 1 变成 2（也能够不变）
• 将 2 变成 1（也能够不变）
• 将 3 变成 6（也能够不变）
• 将 4 变成 2 或 1（也能够不变）

用图来示意就是上面这样的：

这不就相当于: 从 [[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)

技巧三 – 预先小诸葛

这个技巧指的是：当从左到右遍历的时候，咱们是不晓得左边是什么的，须要等到你到了左边之后才晓得。

如果想晓得左边是什么，一种简略的形式是遍历两次，第一次遍历将数据记录下来，当第二次遍历的时候，用上次遍历记录的数据。这是咱们应用最多的形式。不过有时候，咱们也能够在遍历到指定元素后，往前回溯，这样就能够边遍历边存储，应用一次遍历即可。具体来说就是将从左到右的数据全副收集起来，等到须要用的时候，从外面挑一个用。如果咱们都要取最大值或者最小值且极值会产生变动，就可 应用堆减速。直观上就是应用了时光机回到之前，达到了事后诸葛亮的目标。

这样说 你必定不明确啥意思。没关系，咱们通过几个例子来讲一下。当你看完这些例子之后，再回头看这句话。

871. 最低加油次数

题目形容

汽车从终点登程驶向目的地，该目的地位于登程地位东面 target 英里处。沿途有加油站，每个 station[i] 代表一个加油站，它位于登程地位东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。假如汽车油箱的容量是有限的，其中最后有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车达到加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。为了达到目的地，汽车所必要的最低加油次数是多少？如果无奈达到目的地，则返回 -1。留神：如果汽车达到加油站时残余燃料为 0，它依然能够在那里加油。如果汽车达到目的地时残余燃料为 0，依然认为它曾经达到目的地。示例 1：输出：target = 1, startFuel = 1, stations = []
输入：0
解释：咱们能够在不加油的状况下达到目的地。示例 2：输出：target = 100, startFuel = 1, stations = [[10,100]]
输入：-1
解释：咱们无奈到达目的地，甚至无奈达到第一个加油站。示例 3：输出：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输入：2
解释：咱们登程时有 10 升燃料。咱们开车来到距终点 10 英里处的加油站，耗费 10 升燃料。将汽油从 0 升加到 60 升。而后，咱们从 10 英里处的加油站开到 60 英里处的加油站（耗费 50 升燃料），并将汽油从 10 升加到 50 升。而后咱们开车到达目的地。咱们沿途在 1 两个加油站停泊，所以返回 2。提醒：1 <= target, startFuel, stations[i][1] <= 10^9
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < ... < stations[stations.length-1][0] < target

思路

为了可能取得 最低加油次数 ，咱们必定心愿能不加油就不加油。那什么时候必须加油呢？答案应该是 如果你不加油，就无奈达到下一个目的地的时候。

伪代码形容就是：

cur = startFuel # 刚开始有 startFuel 升汽油
last = 0 # 上一次的地位
for i, fuel in stations:
    cur -= i - last # 走过两个 staton 的耗油为两个 station 的间隔，也就是 i - last
    if cur < 0:
        # 咱们必须在后面就加油，否则到不了这里
        # 然而在后面的哪个 station 加油呢？# 直觉通知咱们应该贪婪地抉择能够加汽油最多的站 i，如果加上 i 的汽油还是 cur < 0，持续加次大的站 j，直到没有更多汽油可加或者 cur > 0

下面说了要抉择能够加汽油最多的站 i，如果加了油还不行，持续抉择第二多的站。这种动静求极值的场景非常适合应用 heap。

具体来说就是：

• 每通过一个站，就将其油量加到堆。
• 尽可能往前开，油只有不小于 0 就持续开。
• 如果油量小于 0，就从堆中取最大的加到油箱中去，如果油量还是小于 0 持续反复取堆中的最大油量。
• 如果加完油之后油量大于 0，持续开，反复下面的步骤。否则返回 -1，示意无奈达到目的地。

那这个算法是如何体现 预先小诸葛 的呢？你能够把本人代入到题目中进行模仿。把本人设想成正在开车，你的指标就是题目中的要求：起码加油次数 。当你开到一个站的时候，你是不晓得你的油量够不够撑持到下个站的，并且就算撑不到下个站，其实兴许在上个站加油会更好。所以 事实中 你无论如何都 无奈晓得在以后站，我是应该加油还是不加油的，因为信息太少了。

那我会怎么做呢？如果是我在开车的话，我只能每次都加油，这样都无奈达到目的地，那必定就无奈达到目的地了。但如果这样能够达到目的地，我就能够说 如果咱们在那个站加油，这个站抉择不加就能够起码加油次数达到目的地了。你怎么不早说呢？这不就是事后诸葛亮么？

这个事后诸葛亮体现在 咱们是等到没油了才去想应该在之前的某个站加油。

所以这个事后诸葛亮实质上解决的是，基于以后信息无奈获取最优解，咱们必须把握全副信息之后回溯。以这道题来说，咱们能够先遍历一边 station，而后将每个 station 的油量记录到一个数组中，每次咱们“预感“到无奈达到下个站的时候，就从这个数组中取最大的。。。。基于此，咱们能够思考应用堆优化取极值的过程，而不是应用数组的形式。

代码

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        stations += [(target, 0)]
        cur = startFuel
        ans = 0

        h = []
        last = 0
        for i, fuel in stations:
            cur -= i - last
            while cur < 0 and h:
                cur -= heapq.heappop(h)
                ans += 1
            if cur < 0:
                return -1
            heappush(h, -fuel)

            last = i
        return ans

(代码 1.3.10)

1488. 防止洪水泛滥

题目形容

你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨的时候，如果第 n 个湖泊是空的，那么它就会装满水，否则这个湖泊会产生洪水。你的指标是防止任意一个湖泊产生洪水。给你一个整数数组 rains，其中：rains[i] > 0 示意第 i 地利，第 rains[i] 个湖泊会下雨。rains[i] == 0 示意第 i 天没有湖泊会下雨，你能够抉择 一个 湖泊并 抽干 这个湖泊的水。请返回一个数组 ans，满足：ans.length == rains.length
如果 rains[i] > 0，那么 ans[i] == -1。如果 rains[i] == 0，ans[i] 是你第 i 天抉择抽干的湖泊。如果有多种可行解，请返回它们中的 任意一个。如果没方法阻止洪水，请返回一个 空的数组。请留神，如果你抉择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你抉择抽干一个空的湖泊，那么将无事产生（详情请看示例 4）。示例 1：输出：rains = [1,2,3,4]
输入：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包含 [1]
第二天后，装满水的湖泊包含 [1,2]
第三天后，装满水的湖泊包含 [1,2,3]
第四天后，装满水的湖泊包含 [1,2,3,4]
没有哪一天你能够抽干任何湖泊的水，也没有湖泊会产生洪水。示例 2：输出：rains = [1,2,0,0,2,1]
输入：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包含 [1]
第二天后，装满水的湖泊包含 [1,2]
第三天后，咱们抽干湖泊 2。所以剩下装满水的湖泊包含 [1]
第四天后，咱们抽干湖泊 1。所以临时没有装满水的湖泊了。第五天后，装满水的湖泊包含 [2]。第六天后，装满水的湖泊包含 [1,2]。能够看出，这个计划下不会有洪水产生。同时，[-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的计划。示例 3：输出：rains = [1,2,0,1,2]
输入：[]
解释：第二天后，装满水的湖泊包含 [1,2]。咱们能够在第三天抽干一个湖泊的水。但第三天后，湖泊 1 和 2 都会再次下雨，所以不论咱们第三天抽干哪个湖泊的水，另一个湖泊都会产生洪水。示例 4：输出：rains = [69,0,0,0,69]
输入：[-1,69,1,1,-1]
解释：任何形如 [-1,69,x,y,-1], [-1,x,69,y,-1] 或者 [-1,x,y,69,-1] 都是可行的解，其中 1 <= x,y <= 10^9
示例 5：输出：rains = [10,20,20]
输入：[]
解释：因为湖泊 20 会间断下 2 天的雨，所以没有没有方法阻止洪水。提醒：1 <= rains.length <= 10^5
0 <= rains[i] <= 10^9

思路

如果下面的题用 事后诸葛亮 形容比拟牵强的话，那前面这两个题能够说很适宜了。

题目阐明了咱们能够在不下雨的时候抽干一个湖泊，如果有多个下满雨的湖泊，咱们该抽干哪个湖呢？显然应该是抽干最近行将被洪水吞没的湖。然而事实中无论如何咱们都不可能晓得将来哪天哪个湖泊会下雨的，即便有天气预报也不行，因而它也不 100% 牢靠。

然而代码能够啊。咱们能够先遍历一遍 rain 数组就晓得第几天哪个湖泊下雨了。有了这个信息，咱们就能够事后诸葛亮了。

“今天天气很好，我开了天眼，今天湖泊 2 会被洪水吞没，咱们明天就先抽干它，否则就洪水泛滥了。”。

和下面的题目一样，咱们也能够不先遍历 rain 数组，再模仿每天的变动，而是间接模仿，即便以后是晴天咱们也不抽干任何湖泊。接着在模仿的过程 记录晴天的状况 ，等到洪水产生的时候，咱们再思考后面 哪一个晴天 应该抽干哪个湖泊。因而这个事后诸葛亮体现在 咱们是等到洪水泛滥了才去想应该在之前的某天采取什么伎俩。

算法：

• 遍历 rain，模仿每天的变动
• 如果 rain 以后是 0 示意以后是晴天，咱们不抽干任何湖泊。然而咱们将以后天记录到 sunny 数组。
• 如果 rain 大于 0，阐明有一个湖泊下雨了，咱们去看下下雨的这个湖泊是否产生了洪水泛滥。其实就是看下下雨前是否曾经有水了。这提醒咱们用一个数据结构 lakes 记录每个湖泊的状况，咱们能够用 0 示意没有水，1 示意有水。这样当湖泊 i 下雨的时候且 lakes[i] = 1 就会产生洪水泛滥。
• 如果以后湖泊产生了洪水泛滥，那么就去 sunny 数组找一个晴天去抽干它，这样它就不会洪水泛滥，接下来只须要放弃 lakes[i] = 1 即可。

这道题没有应用到堆，我是成心的。之所以这么做，是让大家明确 事后诸葛亮 这个技巧并不是堆特有的，实际上这就是一种一般的算法思维，就如同从后往前遍历一样。只不过，很多时候，咱们 事后诸葛亮 的场景，须要动静取最大最小值，这个时候就应该思考应用堆了，这其实又回到文章结尾的 一个核心 了，所以大家肯定要灵便应用这些技巧，不可生吞活剥。

下一道题是一个不折不扣的 事后诸葛亮 + 堆优化 的题目。

代码

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        ans = [1] * len(rains)
        lakes = collections.defaultdict(int)
        sunny = []

        for i, rain in enumerate(rains):
            if rain > 0:
                ans[i] = -1
                if lakes[rain - 1] == 1:
                    if 0 == len(sunny):
                        return []
                    ans[sunny.pop()] = rain
                lakes[rain - 1] = 1
            else:
                sunny.append(i)
        return ans

(代码 1.3.11)

1642. 能够达到的最远修建

题目形容

给你一个整数数组 heights，示意建筑物的高度。另有一些砖块 bricks 和梯子 ladders。你从建筑物 0 开始旅程，一直向前面的建筑物挪动，期间可能会用到砖块或梯子。当从建筑物 i 挪动到建筑物 i+1（下标 从 0 开始）时：如果以后建筑物的高度 大于或等于 下一建筑物的高度，则不须要梯子或砖块
如果以后修建的高度 小于 下一个修建的高度，您能够应用 一架梯子 或 (h[i+1] - h[i]) 个砖块
如果以最佳形式应用给定的梯子和砖块，返回你能够达到的最远建筑物的下标（下标 从 0 开始）。

示例 1：输出：heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
输入：4
解释：从建筑物 0 登程，你能够按此计划实现旅程：- 不应用砖块或梯子达到建筑物 1，因为 4 >= 2
- 应用 5 个砖块达到建筑物 2。你必须应用砖块或梯子，因为 2 < 7
- 不应用砖块或梯子达到建筑物 3，因为 7 >= 6
- 应用惟一的梯子达到建筑物 4。你必须应用砖块或梯子，因为 6 < 9
无奈越过建筑物 4，因为没有更多砖块或梯子。示例 2：输出：heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
输入：7
示例 3：输出：heights = [14,3,19,3], bricks = 17, ladders = 0
输入：3
 

提醒：1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length

思路

咱们能够将梯子看出是有限的砖块，只不过只能应用一次，咱们当然心愿能将好梯用在刀刃上。和下面一样，如果是现实生活，咱们是无奈晓得啥时候用梯子好，啥时候用砖头好的。

没关系，咱们持续应用事后诸葛亮法，一次遍历就可实现。和后面的思路相似，那就是我无脑用梯子，等梯子不够用了，咱们就要开始事后诸葛亮了，要是后面用砖头就好了。那什么时候用砖头就好了呢？很显著就是当初用梯子的时候高度差，比当初的高度差小。

直白点就是当初我用梯子爬了个 5 米的墙，当初这里有个十米的墙，我没梯子了，只能用 10 个砖头了。要是之前用 5 个砖头，当初不就能够用一个梯子，从而省下 5 个砖头了吗？

这提醒咱们将用后面用梯子逾越的建筑物高度差存起来，等到前面梯子用完了，咱们将后面被用的梯子“兑换”成砖头持续用。以下面的例子来说，咱们就能够先兑换 10 个砖头，而后将 5 个砖头用掉，也就是相当于减少了 5 个砖头。

如果后面屡次应用了梯子，咱们优先“兑换”哪次呢？显然是优先兑换 高度差 大的，这样兑换的砖头才最多。这提醒每次都从之前存储的高度差当选最大的，并在“兑换”之后将其移除。这种 动静求极值 的场景用什么数据结构适合？当然是堆啦。

代码

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        h = []
        for i in range(1, len(heights)):
            diff = heights[i] - heights[i - 1]
            if diff <= 0:
                continue
            if bricks < diff and ladders > 0:
                ladders -= 1
                if h and -h[0] > diff:
                    bricks -= heapq.heappop(h)
                else:
                    continue
            bricks -= diff
            if bricks < 0:
                return i - 1
            heapq.heappush(h, -diff)
        return len(heights) - 1

(代码 1.3.12)

四大利用

接下来是本文的最初一个局部《四大利用》，目标是通过这几个例子来帮忙大家坚固后面的常识。

1. topK

求解 topK 是堆的一个很重要的性能。这个其实曾经在后面的 固定堆 局部给大家介绍过了。

这里间接援用后面的话：

“其实求第 k 小的数最简略的思路是建设小顶堆，将所有的数先全副入堆，而后一一出堆，一共出堆 k 次。最初一次出堆的就是第 k 小的数。然而，咱们也可不先全副入堆，而是建设大顶堆（留神不是下面的小顶堆），并维持堆的大小为 k 个。如果新的数入堆之后堆的大小大于 k，则须要将堆顶的数和新的数进行比拟，并将较大的移除。这样能够保障堆中的数是整体数字中最小的 k 个，而这最小的 k 个中最大的（即堆顶）不就是第 k 小的么？这也就是抉择建设大顶堆，而不是小顶堆的起因。”

其实除了第 k 小的数，咱们也能够将两头的数全副收集起来，这就能够求出最小的 k 个数。和下面第 k 小的数惟一不同的点在于须要收集 popp 进去的所有的数。

须要留神的是，有时候权重并不是本来数组值自身的大小，也能够是间隔，呈现频率等。

相干题目：

• 面试题 17.14. 最小 K 个数
• 347. 前 K 个高频元素
• 973. 最靠近原点的 K 个点

力扣中无关第 k 的题目很多都是堆。除了堆之外，第 k 的题目其实还会有一些 找法则 的题目，对于这种题目则能够通过 分治 + 递归 的形式来解决，具体就不再这里开展了，感兴趣的能够和我留言探讨。

2. 带权最短距离

对于这点，其实我在后面局部也提到过了，只不过过后只是一带而过。原话是“不过 BFS 真的就没人用优先队列实现么？当然不是！比方带权图的最短门路问题，如果用队列做 BFS 那就须要优先队列才能够，因为门路之间是有 权重的差别 的，这不就是优先队列的设计初衷么。应用优先队列的 BFS 实现典型的就是 dijkstra 算法。”

DIJKSTRA 算法次要解决的是图中任意两点的最短距离。

算法的根本思维是贪婪，每次都遍历所有街坊，并从中找到间隔最小的，实质上是一种广度优先遍历。这里咱们借助堆这种数据结构，使得能够在 $logN$ 的工夫内找到 cost 最小的点，其中 N 为 堆的大小。

代码模板：

def dijkstra(graph, start, end):
    # 堆里的数据都是 (cost, i) 的二元祖，其含意是“从 start 走到 i 的间隔是 cost”。heap = [(0, start)]
    visited = set()
    while heap:
        (cost, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        if u == end:
            return cost
        for v, c in graph[u]:
            if v in visited:
                continue
            next = cost + c
            heapq.heappush(heap, (next, v))
    return -1

(代码 1.4.1)

能够看出代码模板和 BFS 根本是相似的。如果你本人将堆的 key 设定为 steps 也可模仿实现 BFS，这个在后面曾经讲过了，这里不再赘述。

比方一个图是这样的：

E -- 1 --> B -- 1 --> C -- 1 --> D -- 1 --> F
 \                                         /\
  \                                        ||
    -------- 2 ---------> G ------- 1 ------

咱们应用邻接矩阵来结构：

G = {"B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}

shortDistance = dijkstra(G, "E", "C")
print(shortDistance)  # E -- 3 --> F -- 3 --> C == 6

会了这个算法模板，你就能够去 AC 743. 网络延迟时间 了。

残缺代码：

class Solution:
    def dijkstra(self, graph, start, end):
        heap = [(0, start)]
        visited = set()
        while heap:
            (cost, u) = heapq.heappop(heap)
            if u in visited:
                continue
            visited.add(u)
            if u == end:
                return cost
            for v, c in graph[u]:
                if v in visited:
                    continue
                next = cost + c
                heapq.heappush(heap, (next, v))
        return -1
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = collections.defaultdict(list)
        for fr, to, w in times:
            graph[fr - 1].append((to - 1, w))
        ans = -1
        for to in range(N):
            # 调用封装好的 dijkstra 办法
            dist = self.dijkstra(graph, K - 1, to)
            if dist == -1: return -1
            ans = max(ans, dist)
        return ans

(代码 1.4.2)

你学会了么？

下面的算法并不是最优解，我只是为了体现 将 dijkstra 封装为 api 调用 的思维。一个更好的做法是一次遍历记录所有的间隔信息，而不是每次都反复计算。工夫复杂度会大大降低。这在计算一个点到图中所有点的间隔时有很大的意义。为了实现这个目标，咱们的算法会有什么样的调整？

提醒：你能够应用一个 dist 哈希表记录开始点到每个点的最短距离来实现。想进去的话，能够使劲扣 882 题去验证一下哦~

其实只须要做一个小的调整就能够了，因为调整很小，间接看代码会比拟好。

代码：

class Solution:
    def dijkstra(self, graph, start, end):
        heap = [(0, start)]  # cost from start node,end node
        dist = {}
        while heap:
            (cost, u) = heapq.heappop(heap)
            if u in dist:
                continue
            dist[u] = cost
            for v, c in graph[u]:
                if v in dist:
                    continue
                next = cost + c
                heapq.heappush(heap, (next, v))
        return dist
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = collections.defaultdict(list)
        for fr, to, w in times:
            graph[fr - 1].append((to - 1, w))
        ans = -1
        dist = self.dijkstra(graph, K - 1, to)
        return -1 if len(dist) != N else max(dist.values())

(代码 1.4.3)

能够看出咱们只是将 visitd 替换成了 dist，其余不变。另外 dist 其实只是带了 key 的 visited，它这里也起到了 visitd 的作用。

如果你须要计算一个节点到其余所有节点的最短门路，能够应用一个 dist（一个 hashmap）来记录出发点到所有点的最短门路信息，而不是应用 visited（一个 hashset）。

相似的题目也不少，我再举一个给大家 787. K 站直达内最便宜的航班。题目形容：

有 n 个城市通过 m 个航班连贯。每个航班都从城市 u 开始，以价格 w 到达 v。当初给定所有的城市和航班，以及登程城市 src 和目的地 dst，你的工作是找到从 src 到 dst 最多通过 k 站直达的最便宜的价格。如果没有这样的路线，则输入 -1。示例 1：输出:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输入: 200
解释:
城市航班图如下

从城市 0 到城市 2 在 1 站直达以内的最便宜价格是 200，如图中红色所示。示例 2：输出:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输入: 500
解释:
城市航班图如下

从城市 0 到城市 2 在 0 站直达以内的最便宜价格是 500，如图中蓝色所示。提醒：n 范畴是 [1, 100]，城市标签从 0 到 n - 1
航班数量范畴是 [0, n * (n - 1) / 2]
每个航班的格局 (src, dst, price)
每个航班的价格范畴是 [1, 10000]
k 范畴是 [0, n - 1]
航班没有反复，且不存在自环

这道题和下面的没有实质不同，我依然将其封装成 API 来应用，具体看代码就行。

这道题惟一特地的点在于如果直达次数大于 k，也认为无奈达到。这个其实很容易，咱们只须要在堆中用元组来 多携带一个 steps即可，这个 steps 就是 不带权 BFS 中的间隔。如果 pop 进去 steps 大于 K，则认为非法，咱们跳过持续解决即可。

class Solution:
    # 革新一下，减少参数 K，堆多携带一个 steps 即可
    def dijkstra(self, graph, start, end, K):
        heap = [(0, start, 0)]
        visited = set()
        while heap:
            (cost, u, steps) = heapq.heappop(heap)
            if u in visited:
                continue
            visited.add((u, steps))
            if steps > K: continue
            if u == end:
                return cost
            for v, c in graph[u]:
                if (v, steps) in visited:
                    continue
                next = cost + c
                heapq.heappush(heap, (next, v, steps + 1))
        return -1
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        graph = collections.defaultdict(list)
        for fr, to, price in flights:
            graph[fr].append((to, price))
         # 调用封装好的 dijkstra 办法
        return self.dijkstra(graph, src, dst, K + 1)

(代码 1.4.4)

3. 因子合成

和下面两个利用一下，这个我在后面《313. 超级丑数》局部也提到了。

回顾一下丑数的定义：丑数就是质因数只蕴含 2, 3, 5 的正整数。 因而丑数实质就是一个数通过 因子合成 之后只剩下 2，3，5 的整数，而不携带别的因子了。

对于丑数的题目有很多，大多数也能够从堆的角度思考来解。只不过有时候因子个数无限，不应用堆也容易解决。比方：264. 丑数 II 就能够应用三个指针来记录即可，这个技巧在后面也讲过了，不再赘述。

一些题目并不是丑数，然而却明确提到了相似 因子 的信息，并让你求第 k 大的 xx，这个时候优先思考应用堆来解决。如果题目中夹杂一些其余信息，比方 有序，则也可思考二分法。具体应用哪种办法，要具体问题具体分析，不过在此之前大家要对这两种办法都足够相熟才行。

4. 堆排序

后面的三种利用或多或少在后面都提到过。而 堆排序 却未曾在后面提到。

间接考查堆排序的题目简直没有。然而面试却有可能会考查，另外学习堆排序对你了解分治等重要算法思维都有重要意义。个人感觉，堆排序，结构二叉树，结构线段树等算法都有很大的相似性，把握一种，其余都能够举一反三。

实际上，通过后面的堆的学习，咱们能够封装一个堆排序，办法非常简单。

这里我放一个应用堆的 api 实现堆排序的简略的示例代码：

h = [9,5,2,7]
heapq.heapify(h)
ans = []

while h:
    ans.append(heapq.heappop(h))
print(ans) # 2,5,7,9

明确了示例，那封装成 通用堆排序 就不难了。

def heap_sort(h):
    heapq.heapify(h)
    ans = []
    while h:
        ans.append(heapq.heappop(h))
    return ans

这个办法足够简略，如果你明确了后面堆的原理，让你手撸一个堆排序也不难。可是这种办法有个弊病，它不是 原位算法，也就是说你必须应用额定的空间承接后果，空间复杂度为 $O(N)$。然而其实调用完堆排序的办法后，原有的数组内存能够被开释了，因而实践上来说空间也没节约，只不过咱们计算空间复杂度的时候取的是应用内存最多的时刻，因而应用原地算法毫无疑问更优良。如果你切实感觉不爽这个实现，也能够采纳原地的批改的形式。这倒也不难，只不过略微革新一下后面的堆的实现即可，因为篇幅的限度，这里不多讲了。

总结

堆和队列有千头万绪的分割。很多题目我都是先思考应用堆来实现。而后发现每次入堆都是 + 1，而不会跳着更新，比方下一个是 + 2，+3 等等，因而应用队列来实现性能更好。比方 649. Dota2 参议院 和 1654. 到家的起码跳跃次数 等。

堆的核心就一个，那就是 动静求极值。

而求极值无非就是最大值或者最小值，这不难看出。如果求最大值，咱们能够应用大顶堆，如果求最小值，能够用最小堆。而实际上，如果没有动静两个字，很多状况下没有必要应用堆。比方能够间接一次遍历找出最大的即可。而动静这个点不容易看进去，这正是题目的难点。这须要你先对问题进行剖析，剖析出这道题 其实就是动静求极值，那么应用堆来优化就应该被想到。

堆的实现有很多。比方基于链表的跳表，基于数组的二叉堆和基于红黑树的实现等。这里咱们介绍了 两种次要实现 并具体地讲述了二叉堆的实现，不仅是其实现简略，而且其在很多状况下体现都不错，举荐大家重点把握二叉堆实现。

对于二叉堆的实现，外围点就一点 ，那就是始终保护堆的性质不变，具体是什么性质呢？那就是 父节点的权值不大于儿子的权值（小顶堆）。为了达到这个目标，咱们须要在入堆和出堆的时候，应用上浮和下沉操作，并失当地实现元素替换。具体来说就是上浮过程和比它大的父节点进行替换，下沉过程和两个子节点中较小的进行替换，当然前提是它有子节点且子节点比它小。

对于堆化咱们并没有做详细分析。不过如果你了解了本文的入堆操作，这其实很容易。因而堆化自身就是一个一直入堆的过程，只不过 将工夫上的离散的操作变成了一次性操作 而已。

另外我给大家介绍了三个堆的做题技巧，别离是：

• 固定堆，不仅能够解决第 k 问题，还可无效利用曾经计算的后果，防止反复计算。
• 多路归并，实质就是一个暴力解法，和暴力递归没有本质区别。如果你将其转化为递归，也是一种不能记忆化的递归。因而更像是 回溯算法。
• 预先小诸葛。有些信息，咱们在以后没有方法获取，就可用一种数据结构存起来，不便之后”东窗事发“的时候查。这种数据解决能够是很多，常见的有哈希表和堆。你也能够将这个技巧看成是 预先悔恨，有的人比拟能承受这种叫法，不过不论叫法如何，指的都是这个含意。

最初给大家介绍了四种利用，这四种利用除了堆排序，其余在后面或多或少都讲过，它们别离是：

• topK
• 带权最短门路
• 因子合成
• 堆排序

这四种利用实际上还是围绕了堆的一个核心 动静取极值 ，这四种利用只不过是灵便应用了这个特点罢了。因而大家在做题的时候只有死记 动静求极值 即可。如果你可能剖析出这道题和动静取极值无关，那么请务必思考堆。接下来咱们就要在脑子中过一下复杂度，对照一下题目数据范畴就大略能够估算出是否可行啦。

大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858…。目前曾经 39K star 啦。大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。