703. Kth Largest Element in a Stream

Kth Largest Element in a Stream

題目描述：設計一個類別 KthLargest，初始化時給定整數 k 及一個初始數字串列 nums。需要支援 add(val) 操作：在串流中加入一個新數字後，回傳目前所有數字中第 k 大的值。

解題思路：本題的核心是高效地維護「第 k 大的元素」。使用大小為 k 的**最小堆（min-heap）**是最直覺且有效的方法。

關鍵洞察：若堆中始終只保留最大的 k 個數字，則堆頂（最小值）就恰好是第 k 大的元素。

初始化：遍歷 nums 中的每個元素，依序加入堆中；若堆的大小超過 k，彈出堆頂（最小值）。這樣初始化結束後堆中恰好留下最大的 k 個元素。

add(val) 操作：

1. 將 val 推入堆
2. 若堆的大小超過 k，彈出堆頂
3. 回傳堆頂（即第 k 大的元素）

注意：題目保證呼叫 add 時，數字總數必定 ≥ k，因此堆永遠不會在需要回傳時是空的。

時間複雜度：

• 初始化：O(n log k)，其中 n 為 nums 的長度；每次堆操作為 O(log k)
• add(val)：O(log k)，每次最多執行一次推入和一次彈出

空間複雜度：O(k) — 堆中最多維護 k 個元素。

排序後線性搜尋 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)，通常不如最小堆方案實用。

1. 如果 k 本身也可能動態變化（例如支援 setK(newK) 操作），資料結構需要如何調整才能高效處理？
2. 若要同時支援「第 k 大」和「第 k 小」的查詢，能否設計一個統一的資料結構，並分析其時間複雜度？
3. 這道題與「Find Median from Data Stream（295）」都是「維護串流統計量」的經典問題，兩者的設計思路有何共同之處？中位數的雙堆解法能否推廣至第 k 大的問題？