題目描述:設計一個類別 KthLargest,初始化時給定整數 k 及一個初始數字串列 nums。需要支援 add(val) 操作:在串流中加入一個新數字後,回傳目前所有數字中第 k 大的值。
解題思路:本題的核心是高效地維護「第 k 大的元素」。使用大小為 k 的**最小堆(min-heap)**是最直覺且有效的方法。
關鍵洞察:若堆中始終只保留最大的 k 個數字,則堆頂(最小值)就恰好是第 k 大的元素。
初始化:遍歷 nums 中的每個元素,依序加入堆中;若堆的大小超過 k,彈出堆頂(最小值)。這樣初始化結束後堆中恰好留下最大的 k 個元素。
add(val) 操作:
val 推入堆k,彈出堆頂k 大的元素)注意:題目保證呼叫 add 時,數字總數必定 ≥ k,因此堆永遠不會在需要回傳時是空的。
時間複雜度:
nums 的長度;每次堆操作為 O(log k)add(val):O(log k),每次最多執行一次推入和一次彈出空間複雜度:O(k) — 堆中最多維護 k 個元素。
1. Initialize min-heap of size at most k
2. Constructor(k, nums):
a. Store k
b. For each num in nums:
- Push num into min-heap
- If heap size > k: pop the smallest element
3. add(val):
a. Push val into min-heap
b. If heap size > k: pop the smallest element
c. Return heap top (the kth largest element)排序後線性搜尋 O(n log n):每次呼叫 add 時將新元素插入已排序的陣列,再取第 k 大的值。維護有序陣列的插入為 O(n),整體每次 add 是 O(n),不適合頻繁插入的場景。
平衡 BST / 有序集合 O(log n):使用 std::multiset 維護所有元素,每次 add 後用迭代器找到第 k 大的元素(從 rbegin 移動 k-1 步)。雖然支援更靈活的查詢,但常數因子較大,且找第 k 個元素需 O(k) 而非 O(1),通常不如最小堆方案實用。
k 本身也可能動態變化(例如支援 setK(newK) 操作),資料結構需要如何調整才能高效處理?