Kth largest element in a stream of running integers
Implement a class KthLargest to find the kth largest number in a stream. It should have the following methods:
- KthLargest(int k, int [] nums) Initializes the object with the integer k and the initial stream of numbers in nums
- int add(int val) Appends the integer val to the stream and returns the kth largest element in the stream.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Examples:
Input: [KthLargest(3, [1, 2, 3, 4]), add(5), add(2), add(7)]
Output: [null, 3, 3, 4]
Explanation: initial stream = [1, 2, 3, 4], k = 3.
add(5): stream = [1, 2, 3, 4, 5] -> returns 3
add(2): stream = [1, 2, 2, 3, 4, 5] -> returns 3
add(7): stream = [1, 2, 2, 3, 4, 5, 7] -> returns 4
Input: [KthLargest(2, [5, 5, 5, 5], add(2), add(6), add(60)]
Output: [null, 5, 5, 6]
Explanation: initial stream = [5, 5, 5, 5], k = 2.
add(2): stream = [5, 5, 5, 5, 2] -> returns 5
add(6): stream = [5, 5, 5, 5, 2, 6] -> returns 5
add(60): stream = [5, 5, 5, 5, 2, 6, 60] -> returns 6
Input: [KthLargest(4, [5, 1, 2, 7], add(8), add(2), add(6)]
Constraints
- 1 <= Number of instructions <= 1000
- -104 <= val & all initial values <= 104
- 1 <= k <= 104
- k - 1 <= nums.length <= 103
- The stream will have at least k elements during any add call.
Hints
- The smallest element in the heap is the k-th largest element in the stream. Any number smaller than the heap’s root is ignored. Any number larger than the root replaces it, maintaining the top k largest elements.
- "Insert val into the heap if the size is less than k. If the heap already has k elements, compare val with the smallest element: If val > heap[0], replace heap[0] and heapify. If val <= heap[0], discard it."
