設計一個類別，能找到資料流中第 k 大的元素。注意是排序後第 k 大，不是第 k 個不同的元素。實作
KthLargest類別，包含建構子和add方法。
Example:
Input: [“KthLargest”, “add”, “add”, “add”, “add”, “add”] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output: [null, 4, 5, 5, 8, 8]
Intuition
TIP
核心思路：維護一個大小為 k 的 Min Heap，堆頂就是第 k 大的元素。
- 第 k 大的元素 = 從大到小排第 k 個，等價於「前 k 大元素中最小的那個」
- Min Heap 維持大小 k，堆頂自然就是第 k 大
- 每次新增元素時，若 heap 大小超過 k，就彈出最小的（堆頂），確保留下的都是前 k 大
Approaches
1. Sorting — O(n log n) / O(n)
- Idea: 每次
add時，將所有元素排序，取第 k 大的元素 - Time:
O(n log n)每次 add - Space:
O(n)
class KthLargest(k: Int, nums: IntArray) {
private val k = k
private val list = nums.toMutableList()
fun add(`val`: Int): Int {
list.add(`val`)
list.sort()
return list[list.size - k]
}
}⭐ 2. Min Heap — O(log k) / O(k)
- Idea: 用大小為 k 的 Min Heap，堆頂永遠是第 k 大的元素。新增元素時若 heap 大小超過 k，彈出堆頂
- Time:
O(log k)每次 add，建構子O(n log k) - Space:
O(k)
class KthLargest(k: Int, nums: IntArray) {
private val k = k
private val minHeap = PriorityQueue<Int>()
init {
for (num in nums) {
add(num)
}
}
fun add(`val`: Int): Int {
minHeap.offer(`val`)
if (minHeap.size > k) {
minHeap.poll()
}
return minHeap.peek()
}
}🔑 Takeaways
- Pattern: 「第 K 大」問題的標準做法是大小為 k 的 Min Heap
- Key trick: Min Heap 大小固定為 k，堆頂即答案；這個 pattern 適用於所有 Top-K 類問題