個人範例程式碼 - 一刷 (2026/09/04)

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k: # over size k
                heapq.heappop(heap)

        return heap[0] # kth largest

算法說明

只要看到找第 K 大，就直覺先想到 heap。
python 預設內建的 heap 使用方式 「import heapq」

只有 min-heap，如果需要 max-heap，可以使用 -num 存入，是一個處理小技巧。

建立一個 k 大小的 min-heap 後，root 位置就會是第 k 大了。

因為 heap 的特性，我們在子節點能確認比父節點大 (子節點(相對 min) >= 父節點)，至於左節點與右節點哪個更大，這個我們透過 heap 無法知道，在此題目中也不需要知道。

Time Complexity

O(NlogK) # N：掃過 nums，logK 去 K大小的 heap 中找到自己的位置。

Space Complexity

O(K) # heap 的大小

其他 （錯誤紀錄）

第一次做的時候直覺想到了維護 monotonic stack 的解法，大致上是想到維護一個保持 k 大小的 monotonic stack 並始終保持順序，
大致想法是：
(建立並維護一個小到大的 monotonic stack)

1. stack pop 最小
2. 找到適合的位置插入，並移動後面數字順序 # O(logK) + O(K) = O(K)

不過其實光這步就已經不是典型 monotonic stack 會有的操作(push, pop)了，
通常我們使用 monotonic stack 不會有 shifting，這裡應該要改講維護 sorted list

3. 掃過整個 nums # O(N)

整體大概是 O(NK) 比上面作法更慢，且移動處理 stack 顯得複雜了，
heap 的特性更好用，以後看到 kth 大小題型直覺先想到 heap。

例外：除非 nums 中數值進入 heap 順序，會影響掃完的結果，以這題來說，先進後進結果沒差，kth 都一樣。
如果會影響結果，那表示 nums 的順序也非常重要，這時這個方法才有討論的必要。