来自leetcode703题
先构建一个小顶堆类，实现方法可以参考本网站的堆入门
重要方法如下：
- peek()获取堆顶元素
- poll()删除堆顶元素
- poll(int index)删除指定索引处元素
- replace(int replaced)替换堆顶元素
- offer(int offered)堆的尾部添加元素
- offer(int offered)建堆
- down(int parent)下潜
先构建一个k个元素的堆，注意是小顶堆。注意我们不需要全部构建，只要一个k个元素的小顶堆，这样堆顶元素就是第 K 大元素。
比如k=2
然后再将大于堆顶的元素替换即可，replace方法包含下潜实现。
add 方法用于向数据流中添加新元素。如果堆未满，直接将新元素添加到堆中；如果新元素大于堆顶元素，则替换堆顶元素。
这样堆顶元素就是第 K 大元素
代码如下：
package com.dreams.heap;
public class Leetcode703 {
private MinHeap heap;
public Leetcode703(int k, int[] nums) {
heap = new MinHeap(k);
for (int num : nums) {
add(num);
}
}
// 此方法会被不断调用, 模拟数据流中新来的元素
public int add(int val) {
if (!heap.isFull()) {
heap.offer(val);
} else if (val > heap.peek()) {
heap.replace(val);
}
return heap.peek();
}
}测试
public static void main(String[] args) {
Leetcode703 test = new Leetcode703(3,
new int[]{3,4,7,9,2});
System.out.println(test.add(3));
System.out.println(test.add(5));
System.out.println(test.add(10));
System.out.println(test.add(9));
System.out.println(test.add(4));
}输出
参考
https://leetcode.cn/problems/kth-largest-element-in-a-stream/description/
