预计阅读时间：7 分钟
堆
堆只会两招：弹最值、塞新值。但配上贪心，这两招足以打穿一整个题库——反悔堆更是贪心流的后悔药，吃下去连悔棋都是 $O(\log n)$ 的。本合集收录堆类题目。
第 k 大/小
leetcode 264
最小堆解法：先把最小的丑数 1 入堆，每次弹出最小值 x，把 2x、3x、5x 入堆，用哈希表去重。弹 n 次即得第 n 个丑数。
leetcode 373
枚举所有点对至少 $O(n^2)$ 起步，必须利用两数组非递减的性质。想象一个矩阵：纵坐标是 nums1 下标，横坐标是 nums2 下标，矩阵值是数对和。这个矩阵每行非递减、每列也非递减，左上角 (0, 0) 是全局最小。
于是维护一个最小堆：先把第一列整列入堆，然后开始弹。弹出坐标 (i, j) 时补入一个新候选——本应有 (i+1, j) 和 (i, j+1) 两个方向，但第一列已整列入堆，走 (i+1, j) 会重复，所以只补 (i, j+1)，j+1 越界则不补。弹 k 次得到第 k 小点对，时间复杂度 $O(k \log(\min(k, n)))$。
进阶
leetcode 355
模拟 Twitter 推送机制，两种思路：
- 推模式：发推时直接同步给所有粉丝。缺陷是要处理数据污染——follow 时只能加入被关注者本人的推文（此时他的时间线里已混入他自己 followee 的推文，不能整条搬）。
- 拉模式：每人只维护自己发的推文，查询时才从 followee 把推文拉过来合并。这题用拉模式思考代价更小。
leetcode 1354
核心思路：逆向推导 + 大顶堆。
为什么逆向？正向替换的位置太多，是一棵庞大发散的决策树；而数组全为正整数，总和严格单调递增，所以当前的最大值一定是上一轮求出的和——逆推的路径唯一确定。做法：大顶堆每次弹出最大数 num，算出它被替换前的值再塞回去；堆顶变成 1 时说明已退回全 1 初始态，返回 true。
推导公式与取模优化。 每次回退，已知最大数 num 和当前总和 total：
- 剩余和
d = total - num； - 原数本应逐步减：
原数 = num - d - d - ...。极端用例（如[1, 10^9]）会让连续减法 TLE，直接一步取模：next_num = num % d。
四个边界条件，必须按序拦截：
d == 1：直接返回 true。剩余和为 1 说明其他位置全是 1，最大数总能一路减 1 降回 1，必定成功。d == 0：返回 false。数组只剩一个元素且不为 1（为 1 的情况在出队时已判过），无法回退；这一条同时拦下了num % 0的除零崩溃。num <= d：返回 false。最大数还没剩余和大，回退后原数不为正，违反初始全 1（正整数）的设定。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
花费由字母在整个字符串中的总出现次数决定，所以先遍历字符串统计各字母的初始花费，再用最大堆逐个决定填入的字符。注意最后要对选出的字符排序才能保证最小字典序，不能按贪心顺序直接往问号里填。
反悔堆
反悔贪心的常见载体：撤销之前的贪心决策，换成当前更优的决策。反悔贪心并不和堆绑定，经常同堆搭配只是因为贪心需要「高效弹出最值（反悔对象）+ 插入新值」，恰好是堆的本职。
leetcode 1642
先全用砖块贪心走。需要反悔时，用最大堆把耗砖最多的那次爬升换成梯子。
leetcode 630
显然应该先上结束早的课，按结束日期排序后顺序选课。选课途中发现时间超了，就反悔：用最大堆弹出之前耗时最长的课，换成当前这门。
leetcode 871
问最少加几次油能到终点，先按坐标排序。最初的想法是用一个变量维护「能到范围内油量最大的站」，这种贪心有个缺陷：加一次油到不了下一站、但加多次也许能到——「加多次」的分支被丢掉了。把变量换成最大堆即可：堆里存的都是已经路过（可加油）的站，跑不动了就从堆里取最大的加，取到能跑为止，最后看能否到终点。
未完待续，本合集随训练进度持续补完。
本文由 aboom 原创，转载请注明出处。