转载

703. 数据流中的第K大元素

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

import java.util.PriorityQueue;

public class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int kSize;

    public KthLargest(int k, int[] nums) {
        kSize = k;
        minHeap=new PriorityQueue<Integer>(kSize);
        for (int i = 0; i< nums.length; i++){
            add(nums[i]);
        }
    }

    public int add(int val) {
        if (minHeap.size() < kSize){
            minHeap.offer(val);
        }else if (minHeap.peek() < val){
            minHeap.poll();
            minHeap.offer(val);
        }
        return minHeap.peek();
    }
}

Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。

关于堆操作： https://shmilyaw-hotmail-com.iteye.com/blog/1775868

操作说明：

方法名	功能描述
add(Ee)	在队列头部增加一个元素，如果容量已满，则抛出异常，成功则返回true。
clear()	清空
contains(Objecto)	检查是否包含当前参数元素
offer(Ee)	在队列头部增加一个元素，如果容量已满，则返回false，成功加入，返回true。
peek()	返回队列头部节点，但不移除队列头节点。
poll()	将队列头部元素移出队列并返回。
remove(Objecto)	将队列头部元素移出队列并返回，如果队列为空，则抛出异常。
size()	返回长度