題目網址：https://leetcode.cn/problems/kth-largest-element-in-a-stream/

題意：設計一個找到 stream 中第 k 大的元素。注意是排序後的第 k 大元素, 而非第 k 個不同的元素。

實現 KthLargest class：

  • KthLargest(int k, int[] nums)：使用 k 和 nums 來初始化 instance
  • int add(int val)：將 val 加入倒 nums 中, 並返回第 k 大的元素

Solution：

想法：利用 Heap, 使用 min heap pq 來記錄前 k 大的元素, 其中 pq.top() 代表當前第 k 大的元素

  • KthLargest(k, nums)：先 push nums[i], 然後確認 pq.size() 是否 > k。若是的話, 則把 pq.top() 給 pop 掉, 讓 pq 的元素個數維持在 k 個
  • add(val)：先 push val, 然後確認 pq.size() 是否 > k。若是的話, 則把 pq.top() 給 pop 掉, 讓 pq 的元素個數維持在 k 個
class KthLargest {
public:
    KthLargest(int k, vector<int>& nums) {
        k_ = k;
        for (const auto& num : nums) {
            add(num);
        }
    }

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

private:
    int k_;
    priority_queue<int, vector<int>, greater<>> pq; // min heap
};
  • time：
    • KthLargest(k, nums)：$O(n \cdot log(k))$, 其中 n 為 nums 中的元素個數, 因為 heap 要 add / delete 元素皆需花 $O(log(k))$ 來調整 heap
    • add(val)：$O(log(k))$ ➔ heap 要 add / delete 元素皆需花 $O(log(k))$ 來調整 heap
  • space：$O(k)$ ➔ pq 中的元素不超過 k + 1 個