703. Kth Largest Element in a Stream

class KthLargest {
public:
    KthLargest(int k, vector<int>& nums) {
        size = k;
        for(int i = 0;i < nums.size();i++)
        {
            pq.push(nums[i]);
            if(pq.size() > size) pq.pop();
        }
    }
    
    int add(int val) {
        pq.push(val);
        if(pq.size() > size)
            pq.pop();
        return pq.top();
    }
private:
    priority_queue<int, vector<int>, greater<int>> pq; 
    int size;
};

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

优先队列默认使用的comp是less，下面两个完整的示例可以帮助理解C++中的优先队列：

// priority_queue::push/pop
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>
#include <algorithm>
using namespace std;

int main ()
{
  std::priority_queue<int, vector<int>, greater<int>> mypq; 

  mypq.push(30);
  mypq.push(100);
  mypq.push(25);
  mypq.push(40);

  std::cout << "Popping out elements...";
  while (!mypq.empty())
  {
     std::cout << ' ' << mypq.top();
     mypq.pop();
  }
  std::cout << '\n';

  return 0;
}

运行结果:

Popping out elements... 25 30 40 100

// priority_queue::push/pop
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>
#include <algorithm>
using namespace std;

int main ()
{
  std::priority_queue<int> mypq; 

  mypq.push(30);
  mypq.push(100);
  mypq.push(25);
  mypq.push(40);

  std::cout << "Popping out elements...";
  while (!mypq.empty())
  {
     std::cout << ' ' << mypq.top();
     mypq.pop();
  }
  std::cout << '\n';

  return 0;
}

运行结果:

Popping out elements... 100 40 30 25