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

🔗 题目链接

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

📝 题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：

输入：[3,2,1,5,6,4], k = 2
输出：5

输入：[3,2,3,1,2,4,5,5,6], k = 4
输出：4

🧠 思路分析

这道题是“Top K”问题的标准模板。排个序直接取第 k 大的当然行，但排序 O(n log n) 在 n 很大时不是最优。一个更巧妙的办法是用一个大小为 k 的小顶堆：遍历数组，先把前 k 个数放进堆里，然后后面的每个数和堆顶比较，如果比堆顶大，就把堆顶踢出去，把自己加进去。这样遍历完之后，堆顶就是第 k 大的元素。为什么是第 k 大？因为堆里永远保留着当前遇到过的最大的 k 个数，堆顶是这 k 个里最小的，也就是全局第 k 大。时间复杂度 O(n log k)，空间 O(k)。还有一个更快的写法是快速选择（Quick Select），平均 O(n)，但最坏 O(n²)。面试时两种解法都备着最好，先讲堆，再提快选。

💻 代码实现（C++）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
        for (int num : nums) {
            if (pq.size() < k) pq.push(num);
            else if (num > pq.top()) {
                pq.pop();
                pq.push(num);
            }
        }
        return pq.top();
    }
};

📚 相关学习资源

• 文档：LeetCode 官方题解 - 215. 数组中的第K个最大元素（力扣中文站）—— 包含堆、快速选择、排序三种解法，时间复杂度对比清晰，适合当作参考手册。

• 题库：剑指 Offer 40. 最小的k个数（力扣）—— 同类型变体题，做完这道可以顺手刷一下，巩固堆的用法。

• 文档：LeetCode 215：数组中的第K个最大元素（小顶堆）—— 华为云（华为云社区）—— C++ 代码实现小顶堆，提供了“最优解法思路”，适合刷题前快速回顾。

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

⏱ 复杂度分析

• 时间复杂度：O(n log k)，堆操作 log k。

• 空间复杂度：O(k)，堆的大小。

二、347. 前 K 个高频元素

🔗 题目链接

LeetCode 347. 前 K 个高频元素

📝 题目描述

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例：

输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]

输入：nums = [1], k = 1
输出：[1]

🧠 思路分析

这道题比上一道多了一个“频率”的维度。第一步肯定是用哈希表统计每个数字出现的次数。然后问题就变成了：在“次数”里找前 k 大的次数对应的数字。和 215 题几乎一样，只不过比较的对象从数值本身换成了频率。仍然可以用大小为 k 的小顶堆：把哈希表的键值对（数字，频率）往里塞，堆按频率排，最后堆里剩下的 k 个元素就是答案。注意 C++ 的优先队列默认是大顶堆，需要自定义比较函数，或者把频率取负数再塞进去（小技巧）。另外还有一个骚操作是用桶排序：因为频率最大不会超过数组长度，所以可以开一个桶数组，下标表示频率，值存对应的数字，然后从后往前取 k 个。桶排序的时间复杂度 O(n)，但空间大一些。面试时写堆通常够了，因为代码短不容易出错。

💻 代码实现（C++）

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;
        
        // 小顶堆，按频率排序，pair 格式是 {频率, 数字}
        auto cmp = [](pair<int, int>& a, pair<int, int>& b) {
            return a.first > b.first;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        
        for (auto& p : freq) {
            if (pq.size() < k) pq.push({p.second, p.first});
            else if (p.second > pq.top().first) {
                pq.pop();
                pq.push({p.second, p.first});
            }
        }
        
        vector<int> res;
        while (!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};

📚 相关学习资源

• 文档：腾讯云+社区 - 前 K 个高频元素（最小堆解法）（腾讯云+社区）—— 使用“最小堆”思路来维护前k个高频元素，代码清晰，还附带了复杂度分析，C++版参考价值高。

• 文档：CSDN - LeetCode 347. 前K个高频元素（哈希计数、堆与桶排序详解）（CSDN）—— 哈希计数 + 小顶堆 + 桶排序三种解法一网打尽，并提供了 Java 代码实现和详细的复杂度分析。

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

⏱ 复杂度分析

• 时间复杂度：O(n log k)，n 是数组长度。

• 空间复杂度：O(n)，哈希表 + 堆。

三、295. 数据流的中位数

🔗 题目链接

LeetCode 295. 数据流的中位数

📝 题目描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数是中间两个数的平均值。设计一个支持以下两种操作的数据结构：void addNum(int num) 从数据流中添加一个整数到数据结构中；double findMedian() 返回目前所有元素的中位数。

示例：

输入：["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.5,null,2.0]

🧠 思路分析

这道题在力扣上被称为“数据流中位数”，很多大厂面试都爱问。核心思路是维护两个堆：一个大顶堆存较小的一半，一个小顶堆存较大的一半。并且保证大顶堆的大小要么等于小顶堆，要么比小顶堆多一个（这样中位数就能直接从两个堆顶拿到）。每次添加数字时，先根据大小决定放到哪个堆，然后调整两个堆的平衡。具体做法：如果大顶堆为空或者当前数 ≤ 大顶堆堆顶，就扔进大顶堆；否则扔进小顶堆。然后检查大小关系，如果大顶堆比小顶堆多两个，就把大顶堆堆顶挪到小顶堆；如果小顶堆比大顶堆大，就把小顶堆堆顶挪到大顶堆。取中位数时，如果两个堆大小相等，就取两个堆顶的平均值；否则取大顶堆堆顶。所有操作都是 O(log n)，因为堆插入删除是 log 级别。

💻 代码实现（C++）

class MedianFinder {
private:
    priority_queue<int> maxHeap; // 存较小的一半，大顶堆
    priority_queue<int, vector<int>, greater<int>> minHeap; // 存较大的一半，小顶堆
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }
        
        // 平衡两个堆的大小
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        } else {
            return maxHeap.top();
        }
    }
};

📚 相关学习资源

• 文档：labuladong - 用两个二叉堆实现中位数算法（labuladong）—— 从“中位数和中间位置的关系”切入，推导出双堆方法，思路清晰，代码完整，适合深入理解。

• 文档：腾讯云+社区 - 一道简约而不简单的算法题——数据流的中位数（腾讯云+社区）—— 配有动画解析，直观展示了数据插入和堆调整的过程，适合初学者理解双堆的工作流程。

• 文档：CSDN - LeetCode 295. 数据流的中位数（双堆与平衡树详解）（CSDN）—— 提供了双堆的 Java 实现，并严格分析了“平衡左右半部分”的关键细节。

免责声明：以上链接均来自公开网络。若存在侵权问题，请联系删除。

⏱ 复杂度分析

• 时间复杂度：addNum O(log n)，findMedian O(1)。

• 空间复杂度：O(n)，两个堆总共存储 n 个元素。

结语

堆与优先队列篇的三道题，每一道都是 Top K 或中位数问题的教科书式例题。第 K 个最大元素用固定大小的小顶堆维护前 K 大；前 K 个高频元素在统计频率后套用同样的堆思路；数据流的中位数则用两个堆实现了动态取中位数的神奇效果。这三种模型不光在面试里反复出现，在很多真实业务（比如实时排行榜、滑动窗口统计）里也经常用到。把这三种堆的用法刻进脑子里，以后再遇到类似的问题，基本都能秒反应。

下一篇准备写 动态规划之背包问题专题（0-1背包、完全背包、分割等和子集、目标和），这也是面试里的硬骨头。咱们一起啃。

如果本文对你有帮助，欢迎点赞、收藏、转发，你的支持是我持续创作的动力 ❤️

免责声明：本文部分解题思路参考了力扣官方题解及社区优秀文章，相关链接均来自公开网络。若存在侵权问题，请联系删除。