30 秒识别Q1 · 1046 Last Stone Weight：每次取出最重的两块石头相撞，剩下的差值放回去，求最后剩下的重量。你的第一反应是哪个模式？
看答案
堆。「每次取当前最大、处理完再放回去」是堆的标准句式。Python 里全部取负入小顶堆即可。排序做不到——每撞一次集合就变了。
方向最容易记反，记住这一句就够：求第 K 大，用大小为 K 的小顶堆。堆顶是这 K 个里最小的，也就是全局第 K 大；新来的数比堆顶大才有资格挤掉它。求第 K 小就整体取相反数，别去手写大顶堆——Python 3.13 及以前的 heapq 只有小顶堆（3.14 起新增 heappush_max 等，先确认面试环境的版本）。
复杂度是 O(n log K) 而不是排序的 O(n log n)。K 很小时差距巨大，而且它天然支持数据流：数字一个个来，你随时能回答，排序做不到这件事。
| 题面出现… | 想到 |
|---|---|
| 「第 K 大 / 第 K 小」且数组无序 | 大小为 K 的堆（模板 A） |
| 「前 K 个高频 / 最接近原点的 K 个点」 | 模板 A，只换入堆的键 |
| 「数据流 / 不断插入，随时要回答」 | 堆（排序做不到，因为数据没有终点） |
| 「合并 K 个有序链表 / 数组」 | 堆里放 K 个当前头，弹一个补一个 |
| 「动态中位数」 | 对顶堆（模板 B） |
| 「每次取出当前最大的，处理完再放回去」 | 堆（621 任务调度、1046 碰撞石头） |
「前 K 个高频」要先用 Counter 数出频次（第 01 章）再用堆选 K 个——哈希负责统计，堆负责挑选，两步不要混。数组已排序时第 K 大就是一个下标，别掏堆；给的是 BST 时中序走到第 K 个即可（第 07 章）——「第 K」这三个字本身不构成用堆的理由，无序才是；「固定窗口内的最大值」要的是过期淘汰，那是单调队列（第 04 章）不是堆；「第 K 小的距离 / 乘积」这类答案是数值的，回到答案二分（第 05 章）。只要一次的第 K 大且允许平均 O(n)，快速选择（quickselect）也是标准答案。
■ 【骨架】 不变，闭着眼默写 ■ 【插槽】 随题变化，写题前先问自己填什么
import heapq
def kth_largest(nums, k):
heap = [] # 【骨架】小顶堆,堆顶是这 K 个里最小的那个
for x in nums: # 【骨架】
heapq.heappush(heap, x) # 【插槽】入堆的键:值 / 频次 / 距离的相反数
if len(heap) > k: # 【骨架】超员就把最弱的踢出去
heapq.heappop(heap) # 【骨架】
return heap[0] # 【插槽】答案:第 K 大 / 整个 K 集合import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # 【骨架】大顶堆(存相反数),装较小的一半
self.hi = [] # 【骨架】小顶堆,装较大的一半
def add(self, x):
heapq.heappush(self.lo, -x) # 【骨架】先无脑进左边
heapq.heappush(self.hi, -heapq.heappop(self.lo)) # 【骨架】把左边最大的让给右边
if len(self.hi) > len(self.lo): # 【插槽】平衡策略:允许谁多一个
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def median(self):
if len(self.lo) > len(self.hi): # 【插槽】奇数个时中位数在较长的那边
return float(-self.lo[0])
return (-self.lo[0] + self.hi[0]) / 2lo 全体 ≤ hi 全体，且 len(lo) - len(hi) ∈ {0, 1}。「先进左边、再让给右边、右边多了再还回来」这三步能保证不变式恒成立。add 都是「入堆 + 超员就踢」。Counter + 堆的组合。heapq.nlargest(k, cnt, key=cnt.get) 一行也行，但要能说出它内部就是这个堆。桶排序 O(n) 解法是加分项。(maxCount - 1) * (n + 1) + 同频次任务数 这个数学公式。两种都准备，先讲公式再说堆。heappush_max / heappop_max，但面试环境的 Python 未必 ≥ 3.14，先确认版本。对顶堆里 lo 存的是负值，-self.lo[0] 才是真正的最大值——这一步漏掉是 295 最常见的 bug。(freq, val) 里 freq 相同时会去比 val。如果 val 是不可比较的对象（如自定义类、字典），会直接抛 TypeError。塞一个序号当 tie-breaker。heapify 与逐个 push 的差别——heapq.heapify(list) 是 O(n)，逐个 heappush 是 O(n log n)。已经拿到全量数据时用前者；数据流场景只能用后者。30 秒识别Q1 · 1046 Last Stone Weight：每次取出最重的两块石头相撞，剩下的差值放回去，求最后剩下的重量。你的第一反应是哪个模式？
堆。「每次取当前最大、处理完再放回去」是堆的标准句式。Python 里全部取负入小顶堆即可。排序做不到——每撞一次集合就变了。
30 秒识别Q2 · 692 Top K Frequent Words：返回出现频率前 K 高的单词，频率相同的按字典序排。你的第一反应是哪个模式？
Counter + 堆（模板 A）。频率相同按字典序，正是「元组入堆的次级比较」那条翻车点的实战：入堆键写成 (freq, 反向的字典序) 才能一次排对。
30 秒识别Q3 · 658 Find K Closest Elements：给一个已排序数组和目标值 x，找出最接近 x 的 k 个数。你的第一反应是哪个模式？
二分 / 双指针，不是本章——看到「k 个最接近」手就想去掏堆，但数组已排序，答案必然是一段连续区间，二分找左边界即可，O(log n)。堆要先把 n 个元素全扫一遍（O(n log k)），等于把题目给的「有序」这个最强条件原样扔掉。见 §2 分流条件。
每章自测都会混入恰好一道非本章题，防止「读哪章选哪章」的条件反射；题面也一律取自本章未收录的题，避免凭记忆而非凭信号作答。