# 703. Kth Largest Element in a Stream

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your `KthLargest` class will have a constructor which accepts an integer `k` and an integer array `nums`, which contains initial elements from the stream. For each call to the method `KthLargest.add`, return the element representing the kth largest element in the stream.

Example:

``````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
``````

Note:
You may assume that `nums`‘ length ≥ `k-1` and `k` ≥ 1.

``````class KthLargest {
public:
KthLargest(int k, vector<int> nums) {
for (int num : nums) {
q.push(num);
if (q.size() > k) q.pop();
}
K = k;
}

int add(int val) {
q.push(val);
if (q.size() > K) q.pop();
return q.top();
}

private:
priority_queue<int, vector<int>, greater<int>> q;
int K;
};
``````

``````class KthLargest {
public:
KthLargest(int k, vector<int> nums) {
for (int num : nums) {
st.insert(num);
if (st.size() > k) st.erase(st.begin());
}
K = k;
}

int add(int val) {
st.insert(val);
if (st.size() > K) st.erase(st.begin());
return *st.begin();
}

private:
multiset<int> st;
int K;
};
``````

Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-a-stream

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation