堆 數(shù)據(jù)流中的第K大元素

題目

數(shù)據(jù)流中的第K大元素

難度：簡(jiǎn)單

設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第K大元素的類（class）。注意是排序后的第K大元素，不是第K個(gè)不同的元素。

你的 KthLargest 類需要一個(gè)同時(shí)接收整數(shù) k 和整數(shù)數(shù)組nums 的構(gòu)造器，它包含數(shù)據(jù)流中的初始元素。每次調(diào)用 KthLargest.add，返回當(dāng)前數(shù)據(jù)流中第K大的元素。

示例:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

說明: 你可以假設(shè) nums 的長度≥ k-1 且k ≥ 1。

解題

priority_queue<Type, Container, Functional> Type為數(shù)據(jù)類型， Container為保存數(shù)據(jù)的容器，F(xiàn)unctional為元素比較方式。 如果不寫后兩個(gè)參數(shù)，那么容器默認(rèn)用的是vector，比較方式默認(rèn)用operator<，也就是優(yōu)先隊(duì)列是大頂堆，隊(duì)頭元素最大，本題為小頂堆。

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