703. Kth Largest Element in a Stream
Easy
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.
Implement KthLargest class:
KthLargest(int k, int[] nums)Initializes the object with the integerkand the stream of integersnums.int add(int val)Appends the integervalto the stream and returns the element representing thekthlargest element in the stream.
Example 1:
Input ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output [null, 4, 5, 5, 8, 8] Explanation KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
Constraints:
1 <= k <= 1040 <= nums.length <= 104-104 <= nums[i] <= 104-104 <= val <= 104- At most
104calls will be made toadd. - It is guaranteed that there will be at least
kelements in the array when you search for thekthelement.
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.heap = nums
heapq.heapify(self.heap)
self.k = k
while len(self.heap)>k:
heapq.heappop(self.heap)
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap)>self.k:
heapq.heappop(self.heap)
return self.heap[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)