堆
第k大/小
leetcode 264
用最小堆解决，先把最小的丑数1入堆，每次出最小的x，把2x、3x、5x入堆，用哈希表去重。
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(klog(min(k, n)))。
进阶
leetcode 355
模拟twitter推送机制，有两种思路，一种是推模式，发一条推文直接同步给粉丝，这种方式缺陷是需要处理数据污染：即在follow时，只加入他本人的信息（这时他本人的信息中混杂了很多他的followee的信息）。
拉模式想法更简单，每个人只维护自己发的信息，只有在查询时，再从自己的followee把信息拉过来，这题用这种方法思考代价更小。
leetcode 1354
1. 核心思路：逆向推导 + 大顶堆
为什么逆向？ 正向替换数字的位置可能性太多，是一棵庞大且发散的决策树。但观察到题目中全为正整数，数组的总和具有单调性（越加越大），因此当前的“最大值”一定就是上一轮求出的“和”。逆推的路径是唯一确定的。
具体做法： 使用大顶堆（Priority Queue），每次弹出当前数组的最大数（num），计算出它被替换前的值（原数），再将其塞回堆中。当堆顶元素变为 1 时，说明数组已全部退回到了初始状态 [1, 1, 1...]，返回 true。
2. 推导公式与 % 取模优化
每一次的状态回退，已知最大数（新数）和当前总和，未知原数和剩余和：
第一步算剩余和： 剩余和 (d) = 当前总和 (total) - 最大数 (num)
第二步算原数： 原本的逻辑是一步步做减法：原数 = num - d。但为了防止极端用例（如 [1, 10^9]）导致连续减法出现 TLE（超时），直接使用取模优化：next_num = num % d。
3. 四大死亡边界条件（必须按顺序拦截）
在执行取模 num % d 之前或之后，必须拦截以下特殊情况：
1. d == 1：直接返回 true
* 特权情况：只要剩下的数字之和为 1，说明其他位置全是 1。当前的最大数一定可以通过不断减 1，最终降维到 1，必定成功。
2. d == 0：返回 false
* 除零保护：数组只有一个元素（且该元素不是 1 的情况，1 已经在最开始出队时被判定过关了），必定无法退回。拦截此条件可防止后续 num % 0 导致程序崩溃。
3. num <= d：返回 false
* 逻辑非法：最大数还没有剩余的数字之和巨大，说明减去剩余和之后 原数 <= 0。这不符合题目初始状态全为 1（正整数）的规则。
4. num % d == 0：返回 false
* 前身非法：余数为 0 说明这个数字在上一轮完全是由 d 累加出来的，它的前身是 0。同样不符合全为 1 的规则。
4. ⚠️ 避坑指南：数据溢出
题目数据范围：$5 \times 10^4$ 个最大为 $10^9$ 的数字。
求和时总和极容易突破 32 位 int 的最大上限（$2 \times 10^9$）。
对策*：必须使用 64 位整型（long long）来存储 total 以及大顶堆中的元素。在使用 accumulate 初始化求和时，第三个参数必须写成 0LL。
重排元素
leetcode 1054
按需要使用次数贪心，优先选使用次数多的，需要用prev变量记录前一次选的，为了不重复前一次选的要在下次选完后才能重新入最大堆。
leetcode 1405
每一步永远取最多的字符，用最大堆维护，判断：如果最多的会造成三连重复，则取第二多的。本质是贪心
leetcode 3081
花费是由字母在字符串中总到出现次数决定的，因此要先遍历整个字符串得到各字母初始花费，然后用最大堆过一遍得到填入到字符，此时要排序才能保证最小字母序，不能直接贪心的填。
反悔堆
反悔贪心的一种常见做法，撤销之前的贪心操作并采用新的贪心操作。反悔贪心并不和堆绑定，经常和堆结合在一起是因为堆可以高效的弹出最值（反悔）和插入新的值，这是贪心的特点决定的。
leetcode 1642
对砖块贪心，反悔的时候维护一个最大堆，把用砖多的换成梯子。
leetcode 630
显然应该先上结束早的课，先按结束日期排序，在遍历课程时，如果发现前面的课需要花更长时间，需要反悔，用当前课程替换之前的课程，同样用最大堆维护。
leetcode 871
问最少加几次油能到终点，先按坐标排序。开始想的是用一个变量维护，在能到的范围内取最大的。这样贪心有一个缺陷：可能加一次油到不了下一站但是加多次可能就能到，加多次的情况被舍弃了。
因此把变量替换成最大堆，堆里的站点一定是可以到达的，跑不动了去堆里取，取到能跑到为止，最后看能不能到终点。