Go back

LeetCode Hot 100——堆篇（TopK、频率统计、数据流中位数）

LeetCode Hot 100 · 堆篇

堆（Heap）在算法面试里的核心价值只有一句话：在「动态变化」的集合里，用 O(log n) 找到当前的最大值或最小值。它不关心全量有序，只关心「极值」，所以特别适合两类场景——Top-K（只保留前 k 个，随时淘汰最差的）和动态中位数（两个堆各管一半，始终卡在分界线上）。

Hot 100 里「堆」分类的三道题恰好覆盖了这三种经典用法：215 是「小顶堆维护 K 个最大值」、347 是「哈希计数 + 堆筛 Top-K」、295 是「大顶堆 + 小顶堆对半切」。本篇按「面试手撕」的标准重写，每道题都给出暴力解 → 最优解 → 复杂度逐步推导 → CodeTop 真实变体。

215. 数组中的第 K 个最大元素

题意

给定整数数组 nums 和整数 k，返回数组中第 k 大的元素（排序后的第 k 大，注意是「第 k 大」而非「第 k 个不同元素」，重复元素各算一个）。

输入：nums = [3,2,1,5,6,4], k = 2
输出：5   // 排序后 [1,2,3,4,5,6]，倒数第 2 个是 5

难点与易错点

  1. 「第 K 大」要用小顶堆，不是大顶堆。直觉上「找最大」会想到大顶堆，但大顶堆必须把所有 n 个元素装进去再弹 k 次，空间 O(n)。正确做法是小顶堆只留 k 个——堆里始终装着「当前遇到的最大的 k 个」，堆顶恰好是这 k 个里最小的那个，也就是全局第 k 大。
  2. 重复元素各算一个。题目明确「非第 k 个不同元素」，所以 nums = [3,3,3,3], k = 1 的答案是 3，不能去重。
  3. 入堆与弹出的顺序不能反：必须先 offer 再判断 size() > k 弹出，否则会漏掉当前元素直接淘汰、堆永远装不满 k 个。
  4. 边界：k = 1 时答案是最大值，k = n 时答案是最小值；题目保证 1 ≤ k ≤ n，不需要处理非法 k。

题目本质：小顶堆维护 K 个最大值。用大小为 k 的小顶堆遍历数组，当堆大小超过 k 时弹出最小值，最终堆顶就是第 k 大。

现实类比：招聘 Top-K。面试官只保留目前最优的 k 份简历（小顶堆），每来一份新简历，若比「现有 k 份里最差的」还好就替换进来，最后这 k 份里最差的那份，就是整体第 k 强。

容器选择：PriorityQueue<Integer>（Java 默认小顶堆），全程保持堆的大小不超过 k。

解法一：暴力 / 直观（排序）

把数组整体升序排序，倒数第 k 个（nums[n-k]）就是第 k 大。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);               // 全量升序排序
        return nums[nums.length - k];    // 第 k 大 = 倒数第 k 个
    }
}

复杂度逐步推导：Java 对基本类型数组用双轴快排，排序 O(n log n)；之后按下标取元素 O(1)。总时间复杂度 O(n log n)，空间取决于排序实现（原地，O(log n) 递归栈）。

瓶颈在哪：我们只关心「第 k 大」这一个元素，排序却把全部 n 个元素都排好了，做了大量「用不到」的工作。当 n 很大、k 很小（比如一百万个数里找第 10 大）时，n log n 的代价远超必要。

解法二：优化 / 最优（小顶堆维护 k 个）

只维护一个大小为 k 的小顶堆，遍历一遍数组，堆顶即答案。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 小顶堆：始终维护「当前遇到的最大的 k 个元素」
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num);          // 元素先入堆

            // 堆大小超过 k，弹出堆顶（当前这 k+1 个里的最小值），淘汰掉非 Top-K 元素
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        return minHeap.peek();           // 堆顶即第 k 大元素
    }
}

复杂度逐步推导（禁止只记结论，一步步推）：

为什么比排序快：排序是 O(n log n)，堆解是 O(n log k)。当 k << n 时（海量数据取 Top-10），log k 远小于 log n，差距巨大；即使 k 逼近 n，二者也只差一个常数。这是「只维护局部信息，不追求全局有序」的思想红利。

💭 思考：找「第 K 大」为什么用小顶堆，而不是直觉上的大顶堆？——先想清楚诉求：我们只关心「最大的 k 个」，不关心其余。大顶堆要装进全部 n 个再弹 k 次，空间 O(n)；小顶堆只留 k 个，堆顶恰好是「这 k 个里最小的」即全局第 k 大，空间 O(k)。再想排序为什么「亏」：它把全部 n 个都排好了，而我们只取一个元素，做了大量用不到的工作。看到「动态/海量集合里取第 K 大」这个信号，就锁定「大小为 k 的小顶堆，超了就弹」——这是把 O(n log n) 压到 O(n log k) 的核心。

多解法对比

解法时间复杂度空间复杂度适用场景
全量排序O(n log n)O(log n)数据量小，或干脆要返回「完整有序」
小顶堆维护 k 个O(n log k)O(k)本题标准解，k 远小于 n 时优势巨大
快速选择（QuickSelect）O(n) 平均 / O(n²) 最坏O(log n)只关心一个元素、可接受打乱数组时更快

本题约束下 n 可达 10⁵，排序 O(n log n) 能过但非最优；小顶堆 O(n log k) 是面试必须写出的标准答案，代码短、不易错、空间只占 O(k)。快速选择 O(n) 平均更快，但要处理 partition 与最坏退化，手撕容易翻车——面试时先交堆解，再主动提快选才是最优策略。

CodeTop 变体

347. 前 K 个高频元素

题意

给定整数数组 nums 和整数 k，返回出现频率前 k 高的元素，顺序可以任意。

输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]   // 1 出现 3 次、2 出现 2 次，是频率最高的两个

难点与易错点

  1. 比较器要按「频率」而不是「元素值」排序。堆里存的是 [元素值, 频率] 二元组，比较时必须用 a[1] - b[1]，新手常误写成按 a[0]（元素值）排，结果选出的是「值最小的 k 个」而非「频率最高的 k 个」。
  2. 比较器减法溢出：a[1] - b[1] 在本题频率 ≤ n ≤ 10⁵ 时不会溢出，但养成习惯用 Integer.compare(a[1], b[1]) 或 Comparator.comparingInt 更稳健（频率差值理论上有溢出风险时要警惕）。
  3. 输出顺序任意：题目不要求结果有序，从堆里直接取出即可，不要去给结果排序（多此一举）。
  4. 边界：k 可能等于「不同元素的个数」（如 [1,1,1,1], k=1），此时堆永远不会弹出任何元素；若 k 大于不同元素个数则返回全部。

题目本质：词频统计 + 小顶堆 Top-K。先用 HashMap 统计频率，再用大小为 k 的小顶堆按频率筛选前 k 名——是 215 的「值比较」换成「频率比较」的升级版。

现实类比：热搜榜 Top-K。统计每个词被搜索的次数（词频 map），维护一个只放 k 个位置的热搜榜（小顶堆），频率最低的那条随时可能被新的更热话题挤掉。

容器选择：Map<Integer, Integer> 统计频率（merge 一行搞定累加）；PriorityQueue<int[]> 按频率维护小顶堆，比较器 (a, b) -> a[1] - b[1]。

解法一：暴力 / 直观（统计 + 全量排序）

先 HashMap 统计频率，再把所有「元素-频率」按频率降序全量排序，取前 k 个。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计词频
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.merge(num, 1, Integer::sum);
        }

        // 2. 所有 entry 按频率降序全量排序
        List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freq.entrySet());
        entries.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));

        // 3. 取前 k 个的 key
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = entries.get(i).getKey();
        }
        return res;
    }
}

复杂度逐步推导：统计频率遍历 n 个元素 O(n)；设不同元素有 m 个（m ≤ n），对 m 个 entry 排序 O(m log m)，最坏 m = n 时是 O(n log n)；取前 k 个 O(k)。总时间 O(n log n)，空间（map + list）O(n)。

瓶颈在哪：我们又做了一次「全量排序」，但只需要前 k 个。此外 m 通常远小于 n（大量重复元素），却还是被排序拖到了 O(m log m)。

解法二：优化 / 最优（词频统计 + 小顶堆）

只维护一个大小为 k 的「按频率」小顶堆，把 215 的模板套过来。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计词频，Java 8 merge 一行完成累加
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.merge(num, 1, Integer::sum);
        }

        // 2. 小顶堆：按频率排序，存 [元素值, 频率]，堆顶是频率最低的那个
        PriorityQueue<int[]> minHeap =
                new PriorityQueue<>((a, b) -> a[1] - b[1]);

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            minHeap.offer(new int[]{entry.getKey(), entry.getValue()});
            if (minHeap.size() > k) {
                minHeap.poll();       // 淘汰频率最低的，保住高频 Top-K
            }
        }

        // 3. 把堆中剩余的 k 个元素的 key 取出来（顺序任意）
        return minHeap.stream()
                      .mapToInt(pair -> pair[0])
                      .toArray();
    }
}

复杂度逐步推导（一步步推，别只背 O(n log k)）：

与 215 的差异：多了一个「统计频率」的前置步骤（O(n)），堆的比较器从「按值」换成「按频率」，其余骨架完全一致。

💭 思考：为什么 347 是 215 的「换皮」，多出来的词频统计又带来了什么？——先看清 215 的骨架：小顶堆维护 k 个「最值」。347 只是把「比较度量」从元素值换成频率，所以前面多一步 HashMap 统计词频，堆里存 [元素值, 频率] 二元组、比较器按 a[1] 排。再想约束红利：因为每个元素的频率最多是 n，所以还能更进一步——用「桶排序」，把频率 i 的元素放进第 i 个桶，从高到低取 k 个，做到 O(n)。看到「前 K 高频 / Top-K 按某个度量」这个信号，先套 215 的堆模板，再顺手提一句「度量有上界时可用桶排序到线性」，是展示约束敏感度的加分点。

多解法对比

解法时间复杂度空间复杂度适用场景
统计 + 全量排序O(n log n)O(n)不同元素很少、或干脆要完整频率榜
哈希 + 小顶堆O(n log k)O(n)本题标准解，k 远小于 n 时最快
哈希 + 桶排序O(n)O(n)频率有上界（≤ n）时进一步优化到线性

本题约束下 n ≤ 10⁵，k 常远小于 n，堆解 O(n log k) 是标准答案。面试亮点：主动补一句「因为每个元素的频率最多为 n，所以还能用『桶排序』——把频率 i 的元素放进第 i 个桶，从高到低取 k 个，做到 O(n)」，能体现对约束条件的敏感。

CodeTop 变体

295. 数据流的中位数

题意

设计一个 MedianFinder 类，addNum(int num) 向数据结构里追加一个整数，findMedian() 返回当前所有元素的中位数（有序序列中间的数；偶数个时取中间两个的平均）。

输入：addNum(1) → addNum(2) → findMedian() → 1.5 → addNum(3) → findMedian() → 2.0

难点与易错点

  1. 两个堆各管一半，且「下半」多一个。大顶堆 lowerMax 存较小的一半、小顶堆 upperMin 存较大的一半，始终保证 lowerMax.size() == upperMin.size() 或 lowerMax.size() == upperMin.size() + 1（下半可多一个）。一旦方向搞反（上半多一个），中位数取值逻辑就全乱。
  2. 插入的「两跳」顺序不能错：新数必须先入 lowerMax、再把 lowerMax 堆顶（较大一半里最大的）转移到 upperMin，这样才能保证「upperMin 所有元素 ≥ lowerMax 所有元素」，维持正确的有序划分。
  3. 大顶堆的构造：Java PriorityQueue 默认小顶堆，大顶堆必须 new PriorityQueue<>(Collections.reverseOrder()) 或 (a, b) -> b - a，漏了这一步两堆方向相同，结果全错。
  4. 返回值用 2.0 除：偶数个时写 (lowerMax.peek() + upperMin.peek()) / 2.0，若写成 / 2 就是整数除法，会截断掉小数（3 / 2 = 1 而非 1.5）。
  5. 空流边界：题目保证 findMedian() 在至少有一个元素时才调用，但面试时可主动说明「空时抛异常或返回 0」的处理。

题目本质：两个堆维护动态中位数。大顶堆存较小一半、小顶堆存较大一半，中位数即两堆堆顶（奇数取 lowerMax 顶，偶数取两顶平均）。

现实类比：两组学生按成绩分队。低分队用大顶堆（能 O(1) 知道低分队的最高分）、高分队用小顶堆（能 O(1) 知道高分队的最低分），两队人数差不超过 1，中位数就正好卡在两队分界处。

容器选择：PriorityQueue<Integer> 两个——maxHeap（大顶堆，存较小一半，需 Collections.reverseOrder()）+ minHeap（小顶堆，存较大一半）。

解法一：暴力 / 直观（维护有序列表）

用一个列表存所有数，每次 addNum 用二分找到插入位置保持有序，findMedian 直接按下标取。

class MedianFinder {
    // 有序列表，始终按升序排列
    private final List<Integer> list = new ArrayList<>();

    public void addNum(int num) {
        // 二分查找插入位置，保持有序
        int idx = Collections.binarySearch(list, num);
        if (idx < 0) idx = -idx - 1;   // 转成插入点
        list.add(idx, num);            // 插入位置之后的元素都要后移，O(n)
    }

    public double findMedian() {
        int n = list.size();
        if (n % 2 == 1) {
            return list.get(n / 2);                                  // 奇数个，正中
        }
        return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;        // 偶数个，中间两数平均
    }
}

复杂度逐步推导：addNum 里二分查找 O(log n)，但 list.add(idx, num) 需要把 idx 之后的元素整体后移，最坏 O(n)，所以单次 addNum 是 O(n)；findMedian 直接下标取 O(1)。连续插入 n 次累计 O(n²)。空间 O(n)。

瓶颈在哪：每次插入都要移动数组元素，「维护有序」本身很贵。数据流场景下 addNum 是高频操作，O(n) 的插入在 n 大时不可接受。

解法二：优化 / 最优（大顶堆 + 小顶堆对半切）

用两个堆把数据切成「较小一半 / 较大一半」，中位数从两个堆顶 O(1) 读出。

class MedianFinder {
    // lowerMax（大顶堆）存较小的一半，堆顶是较小一半里的最大值
    private final PriorityQueue<Integer> lowerMax =
            new PriorityQueue<>(Collections.reverseOrder());
    // upperMin（小顶堆）存较大的一半，堆顶是较大一半里的最小值
    private final PriorityQueue<Integer> upperMin = new PriorityQueue<>();

    public void addNum(int num) {
        // 第一步：新数先入 lowerMax，再把 lowerMax 的最大值转移到 upperMin
        //        保证 upperMin 里所有元素都 >= lowerMax 里所有元素（两堆有序划分）
        lowerMax.offer(num);
        upperMin.offer(lowerMax.poll());

        // 第二步：保持 lowerMax.size() >= upperMin.size()（下半可多一个，中位数偏向 lowerMax 顶）
        if (upperMin.size() > lowerMax.size()) {
            lowerMax.offer(upperMin.poll());
        }
    }

    public double findMedian() {
        if (lowerMax.size() > upperMin.size()) {
            // 奇数个元素，中位数是较小一半的最大值
            return lowerMax.peek();
        }
        // 偶数个元素，中位数是两堆堆顶的平均值
        return (lowerMax.peek() + upperMin.peek()) / 2.0;
    }
}

复杂度逐步推导（一步步推）：

为什么这是最优：中位数只依赖「中间那一两个数」，我们不需要全序，只需要「较小一半的最大」和「较大一半的最小」——恰好是两个堆顶。把每次 add 的代价从 O(n) 压到 O(log n)，同时 findMedian 保持 O(1)，是数据流场景的教科书解。

💭 思考：数据流中位数为什么是「两个堆对半切」，而不是维护有序列表？——先看有序列表为什么不行：addNum 要二分找位置 + 数组后移，插入 O(n)，数据流场景高频调用直接超时。关键认知：中位数只依赖「中间那一两个数」，等价于「较小一半的最大值」和「较大一半的最小值」——这两个正是堆顶。于是用大顶堆存较小一半、小顶堆存较大一半，插入时走「先入 lowerMax、再把堆顶转移到 upperMin」的两跳，保证两堆有序划分，最后根据大小关系平衡两堆。看到「数据流 + 动态取中位数/分位数」这个信号，就锁定「双堆各管一半」。

多解法对比

解法addNumfindMedian空间适用场景
维护有序列表O(n)O(1)O(n)插入极少、查询极多
大顶堆 + 小顶堆O(log n)O(1)O(n)本题标准解，插入查询都频繁

本题是「数据流」场景，addNum 会被反复调用，O(n) 的有序列表插入在 n 大时直接超时；双堆把插入降到 O(log n)、查询保持 O(1)，是唯一满足大规模数据流约束的解法。面试时务必把「两个堆的平衡不变量」讲清楚——这才是本题要考的核心。

CodeTop 变体

小结：堆三题覆盖了「堆」在面试里的三大核心用法——小顶堆 Top-K（215，维护最大的 k 个）、哈希计数 + 堆 Top-K（347，把比较度量换成频率）、双堆对半切（295，动态中位数）。共通心法是：堆只维护你关心的「极值局部」，不追求全局有序——正是这个「局部有序」，把一堆 O(n log n) 的题压成了 O(n log k) 或 O(log n)。

章末提问

  1. #215 为什么找「第 K 大」用小顶堆而不是大顶堆？——结论：因为小顶堆只留 k 个，堆顶恰好是「这 k 个里最小的」即全局第 k 大，空间 O(k)；大顶堆必须装进全部 n 个再弹 k 次，空间 O(n)。
  2. #295 两个堆的平衡不变量是什么？为什么「下半可多一个」？——结论：不变量是 lowerMax.size() == upperMin.size() 或前者多 1，且「上半所有元素 ≥ 下半所有元素」。下半多一个是为了奇数个时中位数直接取 lowerMax 堆顶，取值逻辑统一、不用特判奇偶。
  3. #215 的堆解 O(n log k) 和排序 O(n log n) 差在哪？k 逼近 n 时还有优势吗？——结论：差在把「全局有序」降成「只维护 k 个的局部有序」；k 逼近 n 时二者只差常数、优势消失，但 k 远小于 n 时 log k 远小于 log n，差距巨大，所以它是「海量数据取 Top-K」的标准答案。
Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
LeetCode Hot 100——贪心篇（买卖股票、跳跃游戏、区间划分）
Next Post
LeetCode Hot 100——栈篇（括号匹配、单调栈）