【C++算法】75.优先级队列_数据流中的第 K 大元素

题目链接：

703. 数据流中的第 K 大元素

题目描述：

解法

实际上就是Topk问题

1. 用堆来解决O(n*logk)
2. 基于快排的快速选择算法O(n)

用堆来解决

1. 创建一个大小为k的堆（大根堆[第k大]/小根堆[第k小]）
2. 循环
   1. 依次进堆
   2. 判断堆的大小是否超过k

C++ 算法代码：

class KthLargest 
{
    // 创建一个小根堆（优先队列）
    // greater<int>表示按升序排列，堆顶是最小元素，通过传入比较函数 greater<int>，可以将其改为小根堆
    priority_queue<int, vector<int>, greater<int>> heap;
    int _k; // 保存k值，表示我们需要找第k大的元素
    
public:
    // 构造函数
    KthLargest(int k, vector<int>& nums) 
    {
        _k = k; // 保存k值
        
        // 遍历初始数组，将元素加入堆中
        for(auto x : nums)
        {
            heap.push(x); // 将元素添加到堆中
            
            // 维护堆的大小为k
            // 如果堆的大小超过k，弹出堆顶（最小的元素）
            // 这样堆中始终保存最大的k个元素，且堆顶是第k大的元素
            if(heap.size() > _k) heap.pop();
        }
    }
    
    // 添加新元素并返回第k大的元素
    int add(int val) 
    {
        heap.push(val); // 将新元素添加到堆中
        
        // 维护堆的大小为k
        // 如果堆的大小超过k，弹出堆顶（最小的元素）
        if(heap.size() > _k) heap.pop();
        
        // 返回堆顶元素，即第k大的元素
        return heap.top();
    }
};

/**
 * 使用方法示例:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

图解

例如：k=3，初始数组 nums=[4,5,8,2]：

1. 初始化:
   • 添加4: 堆=[4], 大小=1 < k
   • 添加5: 堆=[4,5], 大小=2 < k
   • 添加8: 堆=[4,5,8], 大小=3 = k
   • 添加2: 堆=[2,4,8], 大小=4 > k，移除最小元素2，堆变为[4,5,8]
   • 此时堆顶是4，即第3大的元素
2. 添加新元素3:
   • 添加3: 堆=[3,4,5,8], 大小=4 > k，移除最小元素3，堆变为[4,5,8]
   • 返回堆顶4，仍是第3大的元素
3. 添加新元素10:
   • 添加10: 堆=[4,5,8,10], 大小=4 > k，移除最小元素4，堆变为[5,8,10]
   • 返回堆顶5，现在是第3大的元素