一.题目
703. 数据流中的第 K 大元素 – 力扣（LeetCode）
二.思路讲解
2.1 思路讲解
本题本质是一个 TopK 问题，要求实时返回数据流中第 k 大的元素。对于 TopK 问题，通常有两种解法：快速选择 和 堆。快速选择更适合静态数据一次性求解，而本题数据流是动态添加的，因此使用堆更为合适。我们只需维护一个大小为 k 的小根堆，堆中存放当前最大的 k 个元素，堆顶就是第 k 大的元素。
2.2 求第K小为什么要建大堆
如果要求第 k 小的元素，则要维护一个大小为 k 的大根堆，堆中存放当前最小的 k 个元素，堆顶即为第 k 小的元素。 举个例子：要求第三小，那么堆中应该存放最小的三个数。当新数比堆顶（当前第三小）还小时，它应该进入堆，并弹出原先最大的（即原来的第三小），堆顶更新为新的第三小。因此需要大根堆来快速淘汰最大的元素，从而保证堆中始终是当前最小的 k 个。同理，求第 k 大则建小根堆，保留最大的 k 个，堆顶即为第 k 大。明白这个这题也是同样的道理！
三.代码演示
class KthLargest
{
priority_queue<int,vector<int>,greater<int>>heap;//小根堆
int _k;//统计第K个
public:
KthLargest(int k, vector<int>& nums)
{
_k = k;
for(const auto& x : nums)
{
heap.push(x);//进堆
//超了说明堆顶不是第K大
if(heap.size() > _k)
heap.pop();
}
}
int add(int val)
{
heap.push(val);//进堆
//超了说明堆顶不是第K大
if(heap.size() > _k)
heap.pop();
return heap.top();
}
};
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest* obj = new KthLargest(k, nums);
* int param_1 = obj->add(val);
*/
四.代码讲解
一、核心思想
本题要求在动态数据流中实时返回第 k 大的元素。 由于数据不断添加，我们只需维护当前最大的 k 个元素，这 k 个元素中的最小值就是第 k 大的元素。 因此，使用一个大小为 k 的小根堆，堆中始终存放当前最大的 k 个数，堆顶即为所求。
二、数据结构选择
-
priority_queue<int, vector<int>, greater<int>> heap：C++ 中的小根堆（最小堆），堆顶是堆中的最小值。
-
int _k：记录 k 值，用于控制堆的大小。
三、构造函数 KthLargest
将传入的 k 保存到成员变量 _k。
遍历初始数组 nums，将每个元素 x 加入堆（heap.push(x)）。
如果堆的大小超过 _k，则弹出堆顶（即移除当前最小的元素），保证堆中始终只有最大的 k 个数。
初始化后，堆顶就是初始数据流中第 k 大的元素（若数据不足 k 个，则堆顶为最小元素，但题目保证初始调用时 nums 长度至少为 1，且后续添加后堆大小会达到 k）。
四、add 函数
将新值 val 加入堆：heap.push(val)。
如果此时堆的大小超过 _k，则弹出堆顶，保持堆大小为 k。
返回当前堆顶（即第 k 大的元素）。
五、关键细节
-
小根堆的作用：通过保留最大的 k 个数，堆顶是这 k 个数中最小的，正是第 k 大的元素。
-
大小控制：每次添加后检查堆大小，若超出 k 则弹出最小值，确保堆中只存储当前最大的 k 个元素。
五、流程图
