算法日常・每日刷题--＜优先级队列＞2

LCR 059. 数据流中的第 K 大元素 - 力扣LeetCodeLCR 059. 数据流中的第 K 大元素 - 设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。请实现 KthLargest 类 * KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。 * int add(int val) 将 val 插入数据流 nums 后返回当前数据流中第 k 大的元素。 示例输入[KthLargest, add, add, add, add, add][[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]输出[null, 4, 5, 5, 8, 8]解释KthLargest kthLargest new KthLargest(3, [4, 5, 8, 2]);kthLargest.add(3); // return 4kthLargest.add(5); // return 5kthLargest.add(10); // return 5kthLargest.add(9); // return 8kthLargest.add(4); // return 8 提示 * 1 k 104 * 0 nums.length 104 * -104 nums[i] 104 * -104 val 104 * 最多调用 add 方法 104 次 * 题目数据保证在查找第 k 大元素时数组中至少有 k 个元素 注意本题与主站 703 题相同 https://leetcode.cn/problems/kth-largest-element-in-a-stream/ [https://leetcode.cn/problems/kth-largest-element-in-a-stream/]https://leetcode.cn/problems/jBjn9C/一、题目描述题目要求设计一个可以持续接收数据流、快速返回第 K 大元素的类KthLargest注意定义将所有数字降序排序后位于第 k 个位置的数允许存在重复数字。 需要实现两个核心方法构造函数KthLargest(int k, vectorint nums)给定 k 和初始数字流完成初始化int add(int val)新增一个数字到数据流返回当前全局第 k 大的值。示例输入k3初始数组[4,5,8,2]依次调用add(3)、add(5)、add(10)、add(9)、add(4)输出4,5,5,8,8解释初始数据流[4,5,8,2]前 3 大数字[4,5,8]第 3 大为 4添加 3 后前 3 大不变返回 4添加 5 后前 3 大[5,5,8]返回 5添加 10 后前 3 大[5,8,10]返回 5添加 9 后前 3 大[8,9,10]返回 8添加 4 后前 3 大不变返回 8。二,最优解法固定容量小根堆最小堆核心原理我们只需要全局最大的 k 个数字不需要存储全部数据使用小根堆堆内最多保存 k 个元素堆的特性堆顶是堆中最小值堆内存放当前前 k 大数字堆顶天然就是全局第 k 大元素。执行流程初始化阶段遍历所有初始数字逐个入堆若堆长度超过 k弹出堆顶最小值该数不属于前 k 大add 新增数字将新数字压入堆若堆大小 k弹出堆顶最小元素直接返回堆顶即为当前第 k 大值。为什么不用大根堆如果使用大根堆会存储全部数据流空间复杂度O(n)且每次取第 k 大需要遍历堆效率低下。小根堆仅存 k 个元素空间、时间双重最优。class KthLargest { priority_queueint ,vectorint,greaterintheap; int _k; public: KthLargest(int k, vectorint nums) { _kk; for(auto e:nums) { heap.push(e); if(heap.size()_k) heap.pop(); } } int add(int val) { heap.push(val); 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); */