🔗 🟢 703. Kth Largest Element in a Stream

tags: `樹(Tree)` `二元樹(Binary Tree)` `二元搜尋樹(BST)` `堆積(Heap)` `排序(Sorting)` `二分搜索(Binary Search)` `資料流(Data Stream)` `設計(Design)`

題意

設計一個類別來找出資料流中第 $k$ 大的元素。注意，是排序後的第 $k$ 大元素，而不是第 $k$ 個不同的元素。

實現 KthLargest 類別：

KthLargest(int k, int[] nums) 使用整數 $k$ 和整數流 $nums$ 初始化對象。
int add(int val) 將 $val$ 添加到資料流中，並返回資料流中第 $k$ 大的元素。

思路：維護一個大小為 $k$ 的最小堆積(Min Heap)

根據題意，一個數在加入到資料流中就不會被移除，因此只需要考慮最大的 $k$ 個元素即可。而在這 $k$ 個元素中，可以使用最小堆積(Min Heap) 來維護其中的最小值，故只需要維護一個大小為 $k$ 的最小堆積 $hp$ 即可，堆頂的元素即為整個資料流中第 $k$ 大的元素。

當新元素 $val$ 被添加到資料流中時，我們將其推入堆積 $hp$ 。如果此時堆積的大小超過 $k$ ，移除堆頂元素，並更新堆頂為新的第 $k$ 大元素。如此，我們便能夠隨時查詢資料流中的第 $k$ 大元素。

複雜度分析

時間複雜度： $\mathcal{O}(n \log k)$ $O (n lo g k)$ ，其中 $n$ $n$ 為資料流的長度。
- 每次插入都需要 $O(\log k)$ 的時間，總共需要插入 $O(n)$ 次。
空間複雜度： $\mathcal{O}(k)$ ，即堆積的大小。

class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.hp = []  # 維護一個大小為 k 的 min heap
        for x in nums:
            self.add(x)

    def add(self, val: int) -> int:
        heappush(self.hp, val)
        if len(self.hp) > self.k:
            heappop(self.hp)
        return self.hp[0]

class KthLargest {
public:
    int k;
    priority_queue<int, vector<int>, greater<int>> pq;
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (int x : nums) add(x);
    }

    int add(int val) {
        pq.push(val);
        if (pq.size() > k) pq.pop();
        return pq.top();
    }
};