第3章｜栈与队列
Unit 11 · 优先队列：只保留当前最有价值的 k 个候选
← Unit 10
U11
Top K FrequentCounter · Min Heap · Priority
Unit 10 · #239窗口内保留仍有资格的候选
候选会因为时间过期或被更晚的大值支配而离开双端队列。
→
Unit 11 · #347全局保留当前最强的 K 个候选
候选不再随窗口过期；容量超过 k 时，淘汰当前入选集合中的最弱者。
共同方法：不要保存全部历史。先定义“谁仍有资格影响最终决策”，再让容器的可访问端始终暴露最该过期、被支配或被淘汰的候选。
不必把所有候选排好序，
只需守住进入前 K 名的门槛。
先把原数组压缩为“元素 → 频次”，再用容量为 k 的最小堆保存当前最强候选。堆顶不是最终答案中最强的元素，而是当前入选集合中最弱、最应该被替换的元素。
LeetCode #347 题目模型统计频次 · 选出 K 个最高频元素 · 返回顺序任意
题目要求
给定整数数组 nums 和整数 k，返回其中出现频率最高的 k 个元素。答案可以按任意顺序返回，并保证答案唯一。
from typing import List
class Solution:
def topKFrequent(
self,
nums: List[int],
k: int
) -> List[int]:
pass
输入、输出与复杂度目标
- 输入：整数数组
nums与合法的k； - 输出：恰好
k个最高频元素，顺序任意； - 主方法：
O(n + m log k)时间，O(m + k)空间，其中m是不同元素数。
示例
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
输出：[1,2]
输入：nums = [1], k = 1
输出：[1]
输出：[1]
数据约束
1 ≤ nums.length ≤ 10⁵-10⁴ ≤ nums[i] ≤ 10⁴1 ≤ k ≤ 不同元素数量- 进阶要求：时间复杂度优于完整排序的
O(n log n)。
Frequency Compression
先用哈希表把 n 个原始元素压缩为 m 个“值—频次”候选，后续只处理不同元素。
Priority Queue
离开顺序由优先级决定。最小堆可以在 O(log k) 时间插入候选，并在 O(1) 时间查看最弱候选。
Retention Threshold
容量达到 k 后，堆顶频次就是当前门槛；更弱候选不会进入最终前 K 名。
Top-K Invariant
处理完任意前缀候选后，堆中恰好保存这些候选里频次最高的至多 k 个元素。
认知任务 1
频次已经统计出来后，哪些元素应该进入前 2 名？
先不考虑堆。点击两个频次最高的候选，确认问题真正要求的是“选出集合”，而不是输出所有候选的完整排名。
主动画区人工选择实验
演示数据：nums = [1,1,1,2,2,3,3,3,3,4]，k = 2从原数组提取频次
频次候选点击候选 1 和 3
容量为 k 的最小堆 根节点 = 当前最弱入选者
当前保留集合 目标大小 k = 2
已处理候选0
堆插入0
堆淘汰0
当前门槛—
Count
Read Candidate
Push
Pop Weakest
Keep Top K
频次为 4 和 3 的候选，应进入前 2 名。此时不需要知道低频候选之间谁排第 3、谁排第 4。
当前状态契约问题必须依赖当前画面
current candidate—
processed values0 / 4
heap (count,value)[]
heap size / k0 / 2
weakest retained—
current action选择答案
核心不变量处理完前 t 个不同元素后，heap 保存其中频次最高的至多 k 个候选；堆顶是入选者中频次最低者。
为什么是最小堆？
容量超过 k 时，需要最快找出并删除“当前入选者中最弱的一个”，正好是最小堆堆顶。
为什么不需要完整排序？
最终只关心谁进入前 k 名，不关心未入选元素之间的完整相对顺序。
根据当前频次卡片，前 2 个高频元素是哪两个？
更小一步：只比较每张卡片上的 frequency，不要按元素值大小排序。
代码补全：把保留门槛编译为 Python本单元主动画采用容量 k 的最小堆
1from typing import List
2from collections import Counter
3import heapq
4
5class Solution:
6 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
7 frequency =
8 heap = []
9
10 for value, count in :
11 heapq.heappush(heap, )
12
13 if :
14
15
16 return
分层提示 1｜先压缩候选 frequency = Counter(nums) 分层提示 2｜容量受限的最小堆 每个候选使用 (count, value)；先 push，只有 len(heap) > k 时才 pop。 分层提示 3｜为什么堆顶是门槛 heap[0] 是当前入选集合中频次最低的候选，因此超容量时应执行 heapq.heappop(heap)。 分层提示 4｜输出契约 #347 允许任意顺序，只需提取堆中每个元组的 value。 请回到填空区独立完成 6 个表达式；查看提示不会解锁迁移。
关于进阶复杂度：最小堆方法为
O(n + m log k)，适合突出优先队列与 k 较小的场景；若严格要求最坏情况始终优于完整排序，可使用按频次建桶的 O(n) 解法。本页在参考答案下方保留桶排序版本。方法边界：本单元选择最小堆，是为了学习“容量为 k 的候选保留器”。若要严格实现 #347 的线性时间进阶，可按频次建立
0...n 的桶并从高频向低频收集；这里保留策略对照，不直接展示第二份完整代码。代码与堆状态逐行联动1 / 18
定义 Solution 类，尚未读取输入。
完成代码联动后进入 LeetCode #692 复合优先级迁移代码补全正确或播放完整轨迹后解锁；查看提示、填入骨架不会解锁。
迁移题：LeetCode #692「前 K 个高频单词」
#347 只要求返回前 K 个高频元素，顺序任意；#692 除了选出前 K 个单词，还规定了完整输出顺序：频次从高到低，同频时字典序从小到大。迁移的核心因此从“维护入选集合”升级为“定义可执行的全序排名”。
原题先行：读清输出契约，再选择 Top-K 工具
先完成题面阅读检查，随后对照 #347 与 #692，并把复合排序规则映射到 Python。
1 认识原题
2 结构对照
3 语义映射
4 官方样例
题目要求与函数签名
给定字符串数组 words 和整数 k，返回出现次数最多的 k 个单词。答案必须按频次降序排列；频次相同时，按字典序升序排列。
from typing import List
class Solution:
def topKFrequent(
self,
words: List[str],
k: int
) -> List[str]:
pass
- 1 ≤ words.length ≤ 500
- 1 ≤ words[i].length ≤ 10
- 单词只含小写英文字母
- 1 ≤ k ≤ 不同单词数量
- 进阶：O(n log k) 时间、O(n) 额外空间
官方示例
示例 1
words = ["i","love","leetcode","i","love","coding"]
k = 2
输出：["i","love"]
示例 2
words = ["the","day","is","sunny","the","the","the","sunny","is","is"]
k = 4
输出：["the","is","sunny","day"]
阅读锚点：示例 1 中 i 与 love 都出现 2 次，但 i 字典序更小，因此必须排在前面。
检查 1：#692 的返回结果可以像 #347 一样任意排序吗？
请选择。
检查 2：两个单词出现次数相同时，谁优先？
请选择。
完成两道读题检查后解锁结构对照。
#347 前 K 个高频元素
候选不同整数元素
第一优先级频次越高越好
并列规则题目保证答案集合唯一，无需定义输出并列顺序
返回契约前 K 个元素，顺序任意
主结构容量 k 的最小堆，堆顶是最弱入选者
#692 前 K 个高频单词
候选不同字符串单词
第一优先级频次越高越好
并列规则字典序越小越好
返回契约必须按“频次降序、字典序升序”输出
主结构使用完整排名键，并让 Top-K 工具按该键返回有序结果
不能只把 word 塞进 #347 的 (count, value) 元组：Python 元组的字典序越小越靠近最小堆顶，但对容量受限的显式保留堆而言，同频时真正“最弱、应该先淘汰”的是字典序更大的单词。为了避免隐藏的比较方向错误，本迁移使用
heapq.nsmallest 和“最佳优先”的排名键。核心变化：从一个频次门槛，升级为能决定最终顺序的复合排名键。
槽位 1｜压缩候选
槽位 2｜定义最佳优先排名
槽位 3｜只选择前 k 个
槽位 4｜满足输出契约
from typing import List
from collections import Counter
import heapq
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
# 完成四个语义槽位后生成代码骨架
已完成 0 / 4 个语义槽位。
官方示例 1：候选排名
执行状态
当前阶段初始化
frequency{}
当前候选—
排名键—
当前前 k[]
最终输出—
点击“下一步”，先统计单词频次。
可选挑战：不看生成骨架，独立重写 #692
Unit 11 Skill：先定义“更好”，再决定用堆保留集合还是输出排名
#347 的重点是用容量 k 的最小堆守住入选门槛；迁移到 #692 后，还要把频次与字典序组合为全序排名，并满足确定的返回顺序。看到 Top-K 时，先区分“只要集合”还是“还要有序输出”。
题号 / 题型#347 · 频次统计 + Top-K
触发信号只要前 k 名，不需要完整排名
核心表示Counter + 容量 k 最小堆
关键不变量堆保存已处理候选中的前 k 名
迁移新增约束#692 必须按复合优先级有序输出
复合排名键(-frequency[word], word)
常见错误只按频次；同频方向写反；返回无序集合
方法选择显式保留堆 / nsmallest / 完整排序
推荐下一题#973 最接近原点的 K 个点