题目

找到一串数字中的第K大元素

在原数组的基础上，每次会不断插入元素

插入的同时要返回插入后第K大的元素

https://leetcode.com/problems/kth-largest-element-in-a-stream/

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

• KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
• int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
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

 

 

思路

tips区别

优先队列：根据自定义的优先级（更大/更小/甚至字母abc），按照优先级大的先出

普通队列：严格的先进先出

example:https://www.liaoxuefeng.com/wiki/1252599548343744/1265120632401152

优先队列经常用在dijsktra迪杰斯特拉算法，最小堆。这题先熟悉优先队列

q=new PriorityQueue<>(k);

经过定义后，q.peek()返回的则是第K大

 

找第K大的元素，即只用管大元素，小元素的顺序不用管

即每次add，

如果add的元素<第K大，那他进不进队列，对第K大都没有影响，直接忽略掉，return peek；

如果add的元素>第K大，则poll/remove排出队列中最小的，offer/add进该元素，更新队列，再return peek

 

代码

class KthLargest {
    PriorityQueue<Integer> q;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k=k;
        q=new PriorityQueue<>(k);//定义返回第K大的数
        for(int n:nums){
            add(n);
        }
    }

    public int add(int val) {
        if(q.size()<k){
            //初始化
            q.offer(val);
        }
        else if(q.peek()<val){
            //只有当加入的值大于第K大时，才更新队列
            q.poll();
            q.offer(val);
        }
        //返回第K大
        return q.peek();
    }
}