预计阅读时间：9 分钟

堆

堆只会两招：弹最值、塞新值。但配上贪心，这两招足以打穿一整个题库——反悔堆更是贪心流的后悔药，吃下去连悔棋都是 $O(\log n)$ 的。本合集收录堆类题目。

第 k 大/小

leetcode 264

最小堆解法：先把最小的丑数 1 入堆，每次弹出最小值 x，把 2x、3x、5x 入堆，用哈希表去重。弹 n 次即得第 n 个丑数，时间复杂度 $O(n \log n)$。

leetcode 373

枚举所有点对至少 $O(n^2)$ 起步，必须利用两数组非递减的性质。想象一个矩阵：纵坐标是 nums1 下标，横坐标是 nums2 下标，矩阵值是数对和。这个矩阵每行非递减、每列也非递减，左上角 (0, 0) 是全局最小。

于是维护一个最小堆：先把第一列的前 $\min(k, n)$ 个入堆（n 是 nums1 的长度；第 k 行以后的格子，上方同列已有 k 个不比它大的，不可能进前 k），然后开始弹。弹出坐标 (i, j) 时补入一个新候选——本应有 (i+1, j) 和 (i, j+1) 两个方向，但第一列的候选已经入堆，走 (i+1, j) 会重复，所以只补 (i, j+1)，j+1 越界则不补。弹 k 次，依次弹出的就是和最小的 k 个数对。每弹一个最多补一个，堆大小始终不超过 $\min(k, n)$，时间复杂度 $O(k \log(\min(k, n)))$。

多路归并与逆向推导

leetcode 355

模拟 Twitter 推送机制，两种思路：

• 推模式：发推时直接写进所有粉丝的时间线。麻烦在关注关系变化时要改已有的时间线：follow 时只能并入被关注者本人发的推文（他的时间线里混着他自己 followee 的推文，不能整条搬），unfollow 时还要把他的推文从时间线里删掉。
• 拉模式：每人只维护自己发的推文（按时间先后），查询时才从 followee 把推文拉过来合并。这题用拉模式思考代价更小。

拉模式的「合并」就是堆的多路归并：把每个 followee（含自己）最新的一条推文放进以时间戳为键的最大堆，弹出最新的一条，再把这条推文作者的下一条（更早的）压进来，弹满 10 条或堆空为止。

leetcode 1354

核心思路：逆向推导 + 大顶堆。

为什么逆向？正向替换的位置太多，是一棵庞大发散的决策树；而数组全为正整数，元素不止一个时每次替换都让总和严格增大，所以当前的最大值一定是上一轮求出的和——逆推的路径唯一确定。做法：大顶堆每次弹出最大数 num，算出它被替换前的值再塞回去；堆顶变成 1 时说明已退回全 1 初始态，返回 true。

推导公式与取模优化。 每次回退，已知最大数 num 和当前总和 total：

1. 剩余和 d = total - num；
2. 原数本应逐步减：原数 = num - d - d - ...。极端用例（如 [1, 10^9]）会让连续减法 TLE，直接一步取模：next_num = num % d。连减不会越过别的数：其余元素的和是 d，所以只要当前值不小于 d，它就不小于其余任何一个数，仍是最大值，下一轮回退的还是它。

四个边界条件，必须按序拦截：

1. d == 1：直接返回 true。剩余和为 1 说明其他位置全是 1，最大数总能一路减 1 降回 1，必定成功。
2. d == 0：返回 false。数组只剩一个元素且不为 1（为 1 的情况在出队时已判过），无法回退；这一条同时拦下了 num % 0 的除零崩溃。
3. num <= d：返回 false。最大数还没剩余和大，回退后原数不为正，违反初始全 1（正整数）的设定。
4. num % d == 0：返回 false。余数为 0 说明它的前身是 0，同样违反全 1 设定。

避坑：数据溢出。 $5 \times 10^4$ 个最大 $10^9$ 的数，求和轻松突破 32 位 int 上限（约 $2 \times 10^9$）。C++ 里 total 和堆中元素都要用 long long，accumulate 初值必须写 0LL。

重排元素

leetcode 1054

按剩余次数贪心，优先放次数最多的。用 prev 记录上一次选的元素：为了不和上一次重复，它要等下一次选完后才允许重新入最大堆。

leetcode 1405

每一步永远取剩余最多的字符，最大堆维护；如果取它会凑成三连，就取第二多的。本质是贪心。

leetcode 3081

字符串的值只取决于每个字母的总出现次数：出现 cnt 次的字母贡献 $\binom{cnt}{2}$，总值是 26 个字母的贡献之和。要让它最小，次数应尽量平均。所以先遍历字符串统计各字母已有的次数，再用最小堆按（次数，字母）逐个决定填入的字符：每次取次数最少的字母，并列时取字典序小的，取完次数加一放回。注意最后要对选出的字符排序才能保证最小字典序，不能按贪心顺序直接往问号里填。

反悔堆

反悔贪心的常见载体：撤销之前的贪心决策，换成当前更优的决策。反悔贪心并不和堆绑定，经常同堆搭配只是因为贪心需要「高效弹出最值（反悔对象）+ 插入新值」，恰好是堆的本职。

leetcode 1642

先全用砖块贪心走，每次爬升的高度都记进最大堆。砖块用成负数时反悔：还有梯子，就把堆顶（耗砖最多的那次爬升）换成梯子、退回它的砖；没有梯子了，说明爬不上这一栋，答案是上一栋的下标。

leetcode 630

显然应该先上结束早的课，按结束日期排序后顺序选课。选课途中发现时间超了，就反悔：用最大堆弹出之前耗时最长的课，换成当前这门。

leetcode 871

问最少加几次油能到终点，先按坐标排序。最初的想法是用一个变量维护「能到范围内油量最大的站」，这种贪心有个缺陷：加一次油到不了下一站、但加多次也许能到——「加多次」的分支被丢掉了。把变量换成最大堆即可：堆里存的都是已经路过（可加油）的站，跑不动了就从堆里取最大的加，取到能跑为止；堆空了还跑不到，就返回 -1。

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。