ORIGIN

LeetCode 703. Kth Largest Element in a Stream

ACM 1 min137 words

Problem description

703. Kth Largest Element in a Stream

Analysis

Maintain a Heap that contains only the K biggest the element. So the K-th element will be the smallest element in the heap.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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);
*/
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|