Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in sorted order, not the kth distinct element.
Use a heap when the next smallest or largest candidate matters more than the full sorted order. Keep stale or no-longer-valid entries from affecting the answer.
Examples
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4
Constraints
- 1 <= k <= nums.length <= 100,000
- -10,000 <= nums[i] <= 10,000