703. Kth Largest Element in a Stream

Easy

Description

設計一個類別，能找到資料流中第 k 大的元素。注意是排序後第 k 大，不是第 k 個不同的元素。實作 KthLargest 類別，包含建構子和 add 方法。

Example:

Input: [“KthLargest”, “add”, “add”, “add”, “add”, “add”] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] Output: [null, 4, 5, 5, 8, 8]

Intuition#

核心思路：維護一個大小為 k 的 Min Heap，堆頂就是第 k 大的元素。

第 k 大的元素 = 從大到小排第 k 個，等價於「前 k 大元素中最小的那個」
Min Heap 維持大小 k，堆頂自然就是第 k 大
每次新增元素時，若 heap 大小超過 k，就彈出最小的（堆頂），確保留下的都是前 k 大

Approaches#

1: Sorting#

概念: 每次 add 時，將所有元素排序，取第 k 大的元素
時間複雜度: O(n log n) 每次 add
空間複雜度: O(n)

class KthLargest(k: Int, nums: IntArray) {
    private val k = k
    private val list = nums.toMutableList()

    fun add(`val`: Int): Int {
        list.add(`val`)
        list.sort()
        return list[list.size - k]
    }
}

⭐2: Min Heap#

概念: 用大小為 k 的 Min Heap，堆頂永遠是第 k 大的元素。新增元素時若 heap 大小超過 k，彈出堆頂
時間複雜度: O(log k) 每次 add，建構子 O(n log k)
空間複雜度: O(k)

class KthLargest(k: Int, nums: IntArray) {
    private val k = k
    private val minHeap = PriorityQueue<Int>()

    init {
        for (num in nums) {
            add(num)
        }
    }

    fun add(`val`: Int): Int {
        minHeap.offer(`val`)
        if (minHeap.size > k) {
            minHeap.poll()
        }
        return minHeap.peek()
    }
}

🔑 Takeaways#

Pattern: 「第 K 大」問題的標準做法是大小為 k 的 Min Heap
關鍵技巧: Min Heap 大小固定為 k，堆頂即答案；這個 pattern 適用於所有 Top-K 類問題