堆————数据流的第k个大的元素

解题思路

一般地，堆和堆排序——解决 "贪心算法及其类似问题" 的利器。

# 思路：我们可以用一个小根堆来做，并且限制堆的大小为k，初始化时把nums的每个数都push到堆中，如果堆的大小大于k，就pop一个元素。对于add方法也是同理。

# 这里使用的数据结构是C++中的“优先队列（priority_queue）"，包含在头文件<queue>中。优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

 1 class KthLargest {
 2 public:
 3     KthLargest(int k, vector<int>& nums) {
 4         l = k;
 5         for(int i=0;i<nums.size();i++){
 6             que.push(nums[i]);
 7             if(que.size() > l) que.pop();
 8         }
 9     }
10     
11     int add(int val) {
12         que.push(val);
13         if(que.size() > l) que.pop();
14         return que.top();
15     }
16 private:
17     priority_queue<int, vector<int>, std::greater<int>> que;//降序，小顶堆，前k个最大的元素
18     int l;    
19 };
20 
21 /**
22  * Your KthLargest object will be instantiated and called as such:
23  * KthLargest* obj = new KthLargest(k, nums);
24  * int param_1 = obj->add(val);
25  */