友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
-
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。 -
int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
示例 1：
输入：
["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); // 返回 4
kthLargest.add(5); // 返回 5
kthLargest.add(10); // 返回 5
kthLargest.add(9); // 返回 8
kthLargest.add(4); // 返回 8
示例 2：
输入：
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
输出：[null, 7, 7, 7, 8]
解释：
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // 返回 7
kthLargest.add(10); // 返回 7
kthLargest.add(9); // 返回 7
kthLargest.add(9); // 返回 8
提示：
-
0 <= nums.length <= 104 -
1 <= k <= nums.length + 1 -
-104 <= nums[i] <= 104 -
-104 <= val <= 104 -
最多调用
add方法104次
思路分析
首先想到的是对顶堆，看题解，发现不需要保留所有元素，直接使用简单的优先队列即可。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-01 15:22:49
*/
class KthLargest {
// 无需保留所有元素，只需一个优先队列即可。
private PriorityQueue<Integer> topLargestQueue
= new PriorityQueue<>((a, b) -> Integer.compare(b, a));
private PriorityQueue<Integer> topSmallestQueue = new PriorityQueue<>();
public KthLargest(int k, int[] nums) {
for (int num : nums) {
topSmallestQueue.offer(num);
if (topSmallestQueue.size() < k) {
continue;
}
topLargestQueue.offer(topSmallestQueue.poll());
}
}
public int add(int val) {
topSmallestQueue.offer(val);
topLargestQueue.offer(topSmallestQueue.poll());
return topLargestQueue.peek();
}
}