Leetcode 703 - Kth Largest Element in a Stream

題目

Problem#

問你能不能設計一個 class 來在一個 stream 中找到第 k 大的元素。

你要實作兩個 function:

• KthLargest(int k, int[] nums) ctor 用來初始化 k 和一開始的數字 nums
• int add(int val) 將 val 加到資料中，你的 class 應能維護現在第 k 大的數字並回傳

測資限制:#

• $1 \le k \le 10^4$

想法#

用 minheap (priority queue) 來維護最小的元素，但限制這個 minheap 最多只能有 k 個元素，當 minheap 元素數量小於 k 時，直接 push 進去。
當 minheap 的元素數量 $\ge$ k 時，在加入時去檢查加入的數字有沒有比 top 還大，如果有，則先 pop 再 push (因為大於目前最小的，如果加入之後會使 minheap 元素數量 $>$ k)
如此一來，minheap 的 top 就變成了第 k 大的數字

• 時間複雜度: 建立 $\mathcal{O}(n\log{n})$, add 操作 $\mathcal{O}(\log{n})$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#