Description
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.
Examples
k = 3, nums = [4,5,8,2][]Initial sorted: [2,4,5,8], 3rd largest=4. Add 3: [2,3,4,5,8], 3rd=5. Add 5: [2,3,4,5,5,8], 3rd=5. Add 10: [2,3,4,5,5,8,10], 3rd=8.
k = 1, nums = [7,2,9], add = [1,8,3][9,9,9]With k=1, the goal is always to find the largest element. Starting with [7,2,9], the largest is 9. After adding 1: [7,2,9,1], largest is still 9. After adding 8: [7,2,9,1,8], largest is still 9. After adding 3: [7,2,9,1,8,3], largest is still 9.
k = 4, nums = [1], add = [6,3,8,2,5][null,null,1,2,3]With k=4, at least 4 elements are needed before a valid result can be returned. Starting with [1], only 1 element exists. After adding 6,3,8: [1,6,3,8] has 4 elements, so the 4th largest is 1. After adding 2: [1,6,3,8,2], sorted is [1,2,3,6,8], 4th largest is 2. After adding 5: [1,6,3,8,2,5], sorted is [1,2,3,5,6,8], 4th largest is 3.
Constraints
- •
1 ≤ k ≤ 10⁴ - •
0 ≤ nums.length ≤ 10⁴