LeetCode 692中等堆

前K个高频单词图解题解

这道题到底在问什么

给定单词列表 words 和整数 k，返回前 k 个出现频率最高的单词。频次相同时，按字典序（字母顺序）从小到大排。

输入: words = ["i","love","leetcode","i","love","coding"], k = 2
输出: ["i","love"]

最优解：一步一步想明白

3为什么用「最小堆」？因为我们要不停淘汰「最该走的」，让它永远浮在堆顶，超员就弹它。难点在比较器是「双重」的：频次升序、同频字典序降序——这样弹掉的总是该淘汰那个。
4数频次。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
5数频次。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
6数频次。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
7频次数完。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
8准备进堆。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
9入堆 i（×2）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
10i 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
11入堆 love（×2）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
12比较 love(×2) 与父 i(×2)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
13上浮：love(×2) 换到上面。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
14love 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
15入堆 leetcode（×1）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
16比较 leetcode(×1) 与父 love(×2)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
17上浮：leetcode(×1) 换到上面。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
18leetcode 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
19弹出堆顶 leetcode(×1)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
20末尾 love 补到堆顶。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
21堆已恢复最小堆。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
22淘汰 leetcode(×1)，堆恢复大小 2。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
23入堆 coding（×1）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
24比较 coding(×1) 与父 love(×2)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
25上浮：coding(×1) 换到上面。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
26coding 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
27弹出堆顶 coding(×1)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
28末尾 love 补到堆顶。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
29堆已恢复最小堆。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
30淘汰 coding(×1)，堆恢复大小 2。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
31堆里最终留下 i(×2) 和 love(×2)（绿色）= 前 2 个高频单词。leetcode 和 coding 频次最低被弹出。两者同频 ×2，按字母序 i 排在 love 前 = 答案 ["i", "love"]。

⚠️ 容易写错的地方

✗ 错：堆只按「频次」比较，忘了字典序

✓ 对：比较器双重排序：频次 + 字典序

频次并列时（如 i 与 love 都 ×2）只比频次会随机取一个，结果不稳定

✗ 错：同频时把字典序方向搞反

✓ 对：最小堆里同频要让「字典序大的」在堆顶先弹

要留下字典序小的，就得把字典序大的当成"更该淘汰"放堆顶

✗ 错：用最大堆装全部再取前 k

✓ 对：用大小 k 的最小堆边入边淘汰

最大堆要建 n 个 O(n log n)；小根堆只留 k 个 O(n log k)

完整代码（Python / C++ / Java）

Python

import heapq
from collections import Counter
def topKFrequent(words, k):
    cnt = Counter(words)            # 1) 数频次
    # 最小堆：堆顶=最该淘汰者
    # 频次小的先出 → 用 fr；同频字母大的先出 → 用 word
    # heapq 是小根堆：fr 直接用，word 取反序则用 (-fr 思路)；
    # 这里把 key 设成 (fr, 反字典序) 让"最该淘汰"在堆顶。
    class W:
        def __init__(s, w, f): s.w, s.f = w, f
        def __lt__(s, o):              # s 比 o 更该淘汰?
            if s.f != o.f: return s.f < o.f      # 频次小者先
            return s.w > o.w                     # 同频字典序大者先
    heap = []
    for w, f in cnt.items():
        heapq.heappush(heap, W(w, f))
        if len(heap) > k:
            heapq.heappop(heap)        # 弹掉最该淘汰者
    # 取出后按 频次降序、同频字典序升序 排成答案
    return [x.w for x in sorted(heap, key=lambda x:(-x.f, x.w))]

C++

vector<string> topKFrequent(vector<string>& words, int k){
    unordered_map<string,int> cnt;
    for(auto& w : words) cnt[w]++;             // 1) 数频次
    // 比较器：返回 true 表示 a 比 b 更该留在堆顶(更该淘汰)
    auto worse = [](const pair<string,int>& a,
                    const pair<string,int>& b){
        if(a.second != b.second)
            return a.second > b.second;        // 频次大的"更不该淘汰"→沉底
        return a.first < b.first;              // 同频字典序小的"更不该淘汰"
    };
    priority_queue<pair<string,int>,
        vector<pair<string,int>>, decltype(worse)> pq(worse);
    for(auto& [w, f] : cnt){
        pq.push({w, f});
        if((int)pq.size() > k) pq.pop();       // 弹掉最该淘汰者
    }
    vector<string> ans(k);
    for(int i = k - 1; i >= 0; --i){ ans[i] = pq.top().first; pq.pop(); }
    return ans;
}

Java

public List<String> topKFrequent(String[] words, int k){
    Map<String,Integer> cnt = new HashMap<>();
    for(String w : words) cnt.merge(w, 1, Integer::sum); // 1) 数频次
    // 最小堆：堆顶=最该淘汰者
    // 双重比较：频次升序；同频时字典序降序(字母大的在堆顶先出)
    PriorityQueue<String> pq = new PriorityQueue<>(
        (a, b) -> cnt.get(a).equals(cnt.get(b))
            ? b.compareTo(a)        // 同频：字典序大的排堆顶
            : cnt.get(a) - cnt.get(b)); // 频次小的排堆顶
    for(String w : cnt.keySet()){
        pq.offer(w);
        if(pq.size() > k) pq.poll();   // 弹掉最该淘汰者
    }
    List<String> ans = new ArrayList<>();
    while(!pq.isEmpty()) ans.add(pq.poll());
    Collections.reverse(ans);  // 堆里升序取出→反转得 频次降序+同频字典序升序
    return ans;
}

复杂度

时间

O(n log k)

n 个不同单词各做一次 O(log k) 的堆操作（比较含字符串比较）

空间

O(n + k)

哈希表 O(n) 存频次，堆 O(k)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着前K个高频单词的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

能不能做到 O(n) 或 O(n log k) 以下？+

可以做到 O(n + k log n)：用桶排序按频次分桶（频次范围 1..n），每个桶内的单词先排好字典序；再从高频桶往低频桶取，凑满 k 个。建桶 O(n)，桶内排序总计 O(n log n) 最坏，但通常远小于此。堆法 O(n log k) 在 k 远小于 n 时已经很优。

PriorityQueue 的比较器写反了会怎样？+

频次方向写反 → 留下的是低频词，整组答案错；字典序方向写反 → 频次对但并列时取了字典序大的那批，部分答案错且不易察觉。所以一定要用并列样例（如本题 i 与 love）回归测试比较器。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把前K个高频单词一步步讲透（全站已上线 905 份讲透，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →前K个高频单词交互动画,逐步看清每一步怎么走

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 692中等堆

前K个高频单词图解题解

这道题到底在问什么

给定单词列表 words 和整数 k，返回前 k 个出现频率最高的单词。频次相同时，按字典序（字母顺序）从小到大排。

输入: words = ["i","love","leetcode","i","love","coding"], k = 2
输出: ["i","love"]

最优解：一步一步想明白

3为什么用「最小堆」？因为我们要不停淘汰「最该走的」，让它永远浮在堆顶，超员就弹它。难点在比较器是「双重」的：频次升序、同频字典序降序——这样弹掉的总是该淘汰那个。
4数频次。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
5数频次。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
6数频次。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
7频次数完。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
8准备进堆。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
9入堆 i（×2）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
10i 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
11入堆 love（×2）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
12比较 love(×2) 与父 i(×2)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
13上浮：love(×2) 换到上面。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
14love 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
15入堆 leetcode（×1）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
16比较 leetcode(×1) 与父 love(×2)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
17上浮：leetcode(×1) 换到上面。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
18leetcode 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
19弹出堆顶 leetcode(×1)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
20末尾 love 补到堆顶。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
21堆已恢复最小堆。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
22淘汰 leetcode(×1)，堆恢复大小 2。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
23入堆 coding（×1）。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
24比较 coding(×1) 与父 love(×2)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
25上浮：coding(×1) 换到上面。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
26coding 入堆完成。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
27弹出堆顶 coding(×1)。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
28末尾 love 补到堆顶。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
29堆已恢复最小堆。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
30淘汰 coding(×1)，堆恢复大小 2。节点显示「单词(×频次)」，堆按「频次 + 字典序」做最小堆——堆顶永远是最该淘汰的（频次最小，同频则字母最大），超过 k 个就弹掉它。
31堆里最终留下 i(×2) 和 love(×2)（绿色）= 前 2 个高频单词。leetcode 和 coding 频次最低被弹出。两者同频 ×2，按字母序 i 排在 love 前 = 答案 ["i", "love"]。

⚠️ 容易写错的地方

✗ 错：堆只按「频次」比较，忘了字典序

✓ 对：比较器双重排序：频次 + 字典序

频次并列时（如 i 与 love 都 ×2）只比频次会随机取一个，结果不稳定

✗ 错：同频时把字典序方向搞反

✓ 对：最小堆里同频要让「字典序大的」在堆顶先弹

要留下字典序小的，就得把字典序大的当成"更该淘汰"放堆顶

✗ 错：用最大堆装全部再取前 k

✓ 对：用大小 k 的最小堆边入边淘汰

最大堆要建 n 个 O(n log n)；小根堆只留 k 个 O(n log k)

完整代码（Python / C++ / Java）

Python

import heapq
from collections import Counter
def topKFrequent(words, k):
    cnt = Counter(words)            # 1) 数频次
    # 最小堆：堆顶=最该淘汰者
    # 频次小的先出 → 用 fr；同频字母大的先出 → 用 word
    # heapq 是小根堆：fr 直接用，word 取反序则用 (-fr 思路)；
    # 这里把 key 设成 (fr, 反字典序) 让"最该淘汰"在堆顶。
    class W:
        def __init__(s, w, f): s.w, s.f = w, f
        def __lt__(s, o):              # s 比 o 更该淘汰?
            if s.f != o.f: return s.f < o.f      # 频次小者先
            return s.w > o.w                     # 同频字典序大者先
    heap = []
    for w, f in cnt.items():
        heapq.heappush(heap, W(w, f))
        if len(heap) > k:
            heapq.heappop(heap)        # 弹掉最该淘汰者
    # 取出后按 频次降序、同频字典序升序 排成答案
    return [x.w for x in sorted(heap, key=lambda x:(-x.f, x.w))]

C++

vector<string> topKFrequent(vector<string>& words, int k){
    unordered_map<string,int> cnt;
    for(auto& w : words) cnt[w]++;             // 1) 数频次
    // 比较器：返回 true 表示 a 比 b 更该留在堆顶(更该淘汰)
    auto worse = [](const pair<string,int>& a,
                    const pair<string,int>& b){
        if(a.second != b.second)
            return a.second > b.second;        // 频次大的"更不该淘汰"→沉底
        return a.first < b.first;              // 同频字典序小的"更不该淘汰"
    };
    priority_queue<pair<string,int>,
        vector<pair<string,int>>, decltype(worse)> pq(worse);
    for(auto& [w, f] : cnt){
        pq.push({w, f});
        if((int)pq.size() > k) pq.pop();       // 弹掉最该淘汰者
    }
    vector<string> ans(k);
    for(int i = k - 1; i >= 0; --i){ ans[i] = pq.top().first; pq.pop(); }
    return ans;
}

Java

public List<String> topKFrequent(String[] words, int k){
    Map<String,Integer> cnt = new HashMap<>();
    for(String w : words) cnt.merge(w, 1, Integer::sum); // 1) 数频次
    // 最小堆：堆顶=最该淘汰者
    // 双重比较：频次升序；同频时字典序降序(字母大的在堆顶先出)
    PriorityQueue<String> pq = new PriorityQueue<>(
        (a, b) -> cnt.get(a).equals(cnt.get(b))
            ? b.compareTo(a)        // 同频：字典序大的排堆顶
            : cnt.get(a) - cnt.get(b)); // 频次小的排堆顶
    for(String w : cnt.keySet()){
        pq.offer(w);
        if(pq.size() > k) pq.poll();   // 弹掉最该淘汰者
    }
    List<String> ans = new ArrayList<>();
    while(!pq.isEmpty()) ans.add(pq.poll());
    Collections.reverse(ans);  // 堆里升序取出→反转得 频次降序+同频字典序升序
    return ans;
}

复杂度

时间

O(n log k)

n 个不同单词各做一次 O(log k) 的堆操作（比较含字符串比较）

空间

O(n + k)

哈希表 O(n) 存频次，堆 O(k)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着前K个高频单词的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

能不能做到 O(n) 或 O(n log k) 以下？+

PriorityQueue 的比较器写反了会怎样？+

想听吴师兄把这道题讲给你听？

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →前K个高频单词交互动画,逐步看清每一步怎么走

前K个高频单词 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

前K个高频单词 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

前K个高频单词图解题解

前K个高频单词图解题解