703. Kth Largest Element in a Stream
Maintain a Heap that contains only the K biggest the element. So the K-th element will be the smallest element in the heap.
12345678910111213141516171819202122232425262728
class KthLargest {public: priority_queue<int, vector<int>, greater<int>> pq; int maxK; KthLargest(int k, vector<int>& nums) { // pq = priority_queue<int, vector<int>, greater<int>>; for(auto i : nums) { pq.push(i); } while(pq.size() > k) { pq.pop(); } maxK = k; } int add(int val) { pq.push(val); if(pq.size() > maxK) pq.pop(); return pq.top(); }};/** * Your KthLargest object will be instantiated and called as such: * KthLargest* obj = new KthLargest(k, nums); * int param_1 = obj->add(val); */