Leetcode刷题100天—703. 数据流中的第 K 大元素(优先队列)—day16

旧城等待， 2022-09-11 01:20 142阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210823195549819][]

设计一个找到数据流中第 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 4
    kthLargest.add(5);   // return 5
    kthLargest.add(10);  // return 5
    kthLargest.add(9);   // return 8
    kthLargest.add(4);   // return 8

提示：

*  1 <= k <= 104
 *  0 <= nums.length <= 104
 *  \-104 <= nums\[i\] <= 104
 *  \-104 <= val <= 104
 *  最多调用 add 方法 104 次
 *  题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package 优先队列;
    
    import java.util.PriorityQueue;
    
    import javax.print.attribute.standard.PDLOverrideSupported;
    
    /* * 3 * https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/ */
    public class _703_数据流中的第K大元素 { 
    // 采用优先队列
    	PriorityQueue<Integer> queue;
    	int k;
    	public  _703_数据流中的第K大元素(int k,int[] nums) { 
    		queue=new PriorityQueue<>();
    		this.k=k;
    // 通过for循环遍历元素存入到队列中
    		for(int num:nums) { 
    // 调用函数
    			add(num);
    		}
    		
    	}
    // 返回值
    	public  int add(int val) { 
    // 如果增加值那么直接入队就可以了
    		queue.offer(val);
    // 如果队列大于设定的k数,直接出队最小的
    		if (queue.size()>k) { 
    			queue.poll();
    		}
    // 返回堆顶元素
    		return queue.peek();
    	}
    
    
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210823195549819]: /images/20220829/b8fd7aea794f4cd1907c5e8232db9a85.png