题目描述

设计一个找到数据流中第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

(小根堆思路) $O(n)$

构造类：

• 构造小根堆，把元素添加进去，一旦小根堆元素个数大于k，则把多余的pop出去，则剩下的小根堆堆顶就是第K大元素

add函数：

• 当add后元素个数大于k，则把多余的pop出去，则剩下的小根堆堆顶就是第K大元素

时间复杂度

基本上O(1) 的add操作，构造小根堆的O(n)时间复杂度

参考文献

C++ 代码

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> q;
    int k;
    KthLargest(int _k, vector<int>& nums) {
        k = _k;
        for(int i = 0; i < nums.size(); i ++) {
            q.push(nums[i]);
            if(q.size() > k) q.pop();
        }
    }

    int add(int val) {
        q.push(val);
        if(q.size() > k) q.pop();
        return q.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */