0703-数据流中的第K大元素

数据流中的第K大元素

方案一

每次第K大的数字都在不停的变化。那么我们其实只关心前K大个数字就可以了，所以我们可以使用一个最小堆来保存前K个数字，当再加入新数字后，最小堆会自动排序，然后把排序后的最小的那个数字去除，则堆中还是K个数字，返回的时候只需返回堆顶元素即可。

C++-源代码

class KthLargest {
public:
    KthLargest(int k, vector<int> nums) {
        
        for(int num : nums) {
            
            q.push(num);
            if (q.size() > k) {
                
                q.pop();
            }
        }
        K = k;
    }
    
    int add(int val) {
        
        q.push(val);
        if (q.size() > K) {
            
            q.pop();
        }
        
        return q.top();
    }
    
    private:
    priority_queue<int, vector<int>, greater<int>> q;
    int K;
};

参考Grandyang