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 sorted order, not the kth distinct element.

Implement the KthLargest class:

• KthLargest(k, nums) - initializes the object with the integer k and the stream of integers nums.
• add(val) - appends val to the stream and returns the element representing the kth largest element in the stream.

---

Example 1

Input: k = 3, nums = [4, 5, 8, 2]
       add(3) -> 4
       add(5) -> 5
       add(10) -> 5
       add(9) -> 8
       add(4) -> 8

Input: k = 3, nums = [4, 5, 8, 2], calls = [add(3), add(5), add(10), add(9), add(4)]
Output: [4, 5, 5, 8, 8]
Explanation: After each add, the stream is sorted descending and the 3rd element is returned.

Example 2

Input: k = 1, nums = [], calls = [add(-3), add(-2), add(-4), add(0), add(4)]
Output: [-3, -2, -2, 0, 4]
Explanation: With k=1 we always return the current maximum; the initial stream is empty.

---

Constraints

• 1 <= k <= 10^4
• 0 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• -10^4 <= val <= 10^4
• At most 10^4 calls will be made to add.
• It is guaranteed that there will be at least k elements in the array when add is called.