优先级队列(堆)-703.数据流中的最大值-力扣(LeetCode)

个人主页：1白天的黑夜1-CSDN博客

专栏：力扣刷题录_1白天的黑夜1的博客-CSDN博客

目录

一、题目解析

1、调用add会返回当前第K大元素

2、add只会调用10^4次

二、算法原理

在讲解法之前，先有一个问题，该题用大根堆还是小根堆呢？

结论：该用小根堆

为什么要用小根堆？

结论：小根堆的性质能以O(1)的效率执行add操作

解法：优先级队列(小根堆)

具体步骤：

三、代码示例

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！

一、题目解析

1、调用add会返回当前第K大元素

2、add只会调用10^4次

二、算法原理

在我们学习堆这个数据结构的时候，或许了解过Tok问题(前k个最大/最小or第k个最大/最小)，这很明显属于Tok问题，我们可以使用堆来解决问题

在讲解法之前，先有一个问题，该题用大根堆还是小根堆呢？

大根堆顾名思义，从根往下，比孩子大的堆，堆顶元素为最大值，而小根堆则相反。回归本题，题目要求的是第k大的元素，我们先用大根堆试试，毕竟存的都是大的元素。由于是第k大，所以可以控制大根堆的个数为k个，最后一个元素就是第k大的元素。这样对吗？我们分析一下，假如给定一组数据{3，{4，5，6}，{2}，{4}，{5}}，预计的结果是{4，4，5}，用我们的大根堆思路推导一下，k=3，以4，5，6先构造大根堆，此时堆顶为6，孩子为4，5，以4，5，6先构造大根堆，此时堆顶为6，孩子为4，5，我们将add的2，加入到大根堆中，此时个数超过k=3，为了维持k的堆个数，所以要pop()掉堆顶数据，此时堆变为堆顶是5，孩子是2，4了，此时返回结果5，可以发现与我们的预计结果不符合

结论：该用小根堆

为什么要用小根堆？

省流版：因为模拟过大根堆行不通，所以该用小根堆

详细版：以上面数据重新模拟，{3，{4，5，6}，{2}，{4}，{5}}，我们先构成出一个大小为k=3的小根堆，此时堆顶元素4，孩子为5，6，将add的2加入堆中，此时堆顶元素为2，孩子为4，5，6，此时堆的个数超过k=3，需要维护k的大小，所以pop掉堆顶元素，此时堆顶元素为4，孩子为5，6，返回结果为4，继续加入4，此时大小又超过k=3，所以继续pop掉堆顶元素，此时结果为4，继续加入5，维护k，此时堆顶元素为5，孩子为5，6，此时返回5

结论：小根堆的性质能以O(1)的效率执行add操作

解法：优先级队列(小根堆)

这三个模板参数分别表示存储的数据类型，用于存储数据的容器，比较器

这里的Compare缺省参数less<typename Container::value_type>，代表priority_queue是大根堆，而小根堆则需要greater<typename Container::value_type>

priority_queue<int，vector<int>，greater<int>> min_heap;

具体步骤：

1、先全局定义出_k和小根堆

2、在构造函数中以k对_k赋值，构造k个大小的小根堆

1、循环插入数据到小根堆中

2、当小根堆的大小超过_k时，pop掉堆顶元素

3、在add函数中将插入的数据加入到小根堆中，如果小根堆的大小超过_k，pop掉堆顶元素，返回top

详细接口信息如果想了解，可以访问链接查询

链接：priority_queue - C++ Reference

三、代码示例

class KthLargest {
public:
    priority_queue<int,vector<int>,greater<int>> pqi;
    int _k;
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for(auto n : nums)
        {
            pqi.push(n);
            if(pqi.size()>_k) pqi.pop();
        }
    }
    
    int add(int val)
    {
        pqi.push(val);
        if(pqi.size()>_k) pqi.pop();
        return pqi.top();
    }
};

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！