Heap、Top-K 與區間實戰：5 題從讀題推導到最優解（LC 215/347/23/56/253）

這篇把兩個面試高頻武器一次練齊：

• Heap（優先佇列）：只要看到「前 K 大 / 前 K 小 / 第 K 個 / 合併 K 路 / 動態取最值」，第一個想到的就是 heap——它讓你用 O(log k) 維護一個「滾動的極值集合」。
• 區間（Intervals）：只要看到「區間合併 / 重疊 / 排程」，幾乎都是先按起點（或端點）排序，再線性掃一遍。

延續一貫的完整推導流程：

📋 題目 → 🧭 拆解 → 暴力 → 瓶頸 → 洞察 → 最優 → 程式碼

• 第 K 大（215）→ Top-K 頻率（347）→ 合併 K 條排序鏈（23）→ 合併區間（56）→ 最少會議室（253）

① LC 215 — Kth Largest Element in an Array

📋 題目：給定整數陣列 nums 與整數 k，回傳陣列中第 k 大的元素（是排序後的第 k 大，不是去重後的）。

範例：nums = [3,2,1,5,6,4], k = 2 → 5；nums = [3,2,3,1,2,4,5,5,6], k = 4 → 4

🌐 EN — Given an integer array nums and integer k, return the kth largest element (the kth largest in sorted order, not the kth distinct). Example: nums = [3,2,1,5,6,4], k = 2 → 5; [3,2,3,1,2,4,5,5,6], k = 4 → 4

🧭 從讀題到解法

1. 拆解：要第 k 大，但不需要完整排序——只關心前 k 大那一小撮。
2. 暴力解：排序後取倒數第 k 個，O(n log n)。能過，但做了多餘的事。
3. 關鍵洞察（size-k 最小堆）：維護一個大小為 k 的最小堆，掃過每個元素就丟進去、超過 k 就彈掉最小的。最後堆裡剩的是「最大的 k 個」，而堆頂（最小的那個）就是第 k 大。
4. 最優解：min-heap，O(n log k)。比排序快（k 小時尤其明顯）。

import heapq

def findKthLargest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)        # drop the smallest, keep k largest
    return heap[0]                      # smallest of the k largest = kth largest

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;   // min-heap
    for (int n : nums) {
        heap.push(n);
        if ((int)heap.size() > k) heap.pop();
    }
    return heap.top();
}

• 複雜度：時間 O(n log k)，空間 O(k)。
• 坑：① 用最小堆裝「最大的 k 個」（反直覺但正確）；② 進階解是 Quickselect，平均 O(n)、最壞 O(n²)，面試講得出來加分；③ heap 解的好處是支援串流資料（資料一直來、隨時要第 k 大）。

② LC 347 — Top K Frequent Elements

📋 題目：給定整數陣列 nums 與整數 k，回傳出現頻率前 k 高的元素（順序不限）。

範例：nums = [1,1,1,2,2,3], k = 2 → [1,2]；nums = [1], k = 1 → [1]

🌐 EN — Given an integer array nums and integer k, return the k most frequent elements (any order). Example: nums = [1,1,1,2,2,3], k = 2 → [1,2]; [1], k = 1 → [1]

🧭 從讀題到解法

1. 拆解：先算每個值的頻率（HashMap），問題就變成「對頻率取 Top-K」——又是 215 那招。
2. 暴力解：算頻率後對所有 (值, 頻率) 排序取前 k，O(n log n)。
3. 關鍵洞察（heap 或 bucket）：① 用 size-k 最小堆對頻率取 Top-K，O(n log k)；② 更妙的是桶排序：頻率最多只到 n，開 n+1 個桶、把值丟進「頻率對應的桶」，再從高頻往低收 k 個——O(n)。
4. 最優解：heap 易寫；bucket 最快。

import heapq
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)   # O(n log k)

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;
    // min-heap by frequency, keep k
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
    for (auto& [num, freq] : count) {
        heap.push({freq, num});
        if ((int)heap.size() > k) heap.pop();
    }
    vector<int> res;
    while (!heap.empty()) { res.push_back(heap.top().second); heap.pop(); }
    return res;
}

💡 進階：O(n) 桶排序（頻率當索引）

from collections import Counter
def topKFrequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]   # index = frequency
    for num, freq in count.items():
        buckets[freq].append(num)
    res = []
    for freq in range(len(buckets) - 1, 0, -1):     # high freq → low
        for num in buckets[freq]:
            res.append(num)
            if len(res) == k:
                return res

• 複雜度：heap O(n log k)、bucket O(n)；空間 O(n)。
• 坑：① 頻率的範圍是 1..n，所以桶開 n+1 個剛好；② 題目保證答案唯一，不用煩惱平手；③ heap 要裝 (頻率, 值)，比較依頻率。

③ LC 23 — Merge k Sorted Lists

📋 題目：給定 k 條已排序的鏈結串列，把它們合併成一條排序鏈並回傳。

範例：lists = [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]

🌐 EN — Given k sorted linked lists, merge them into one sorted list and return it. Example: lists = [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]

🧭 從讀題到解法

1. 拆解：每次要從 k 條鏈的當前頭節點裡挑最小的接上去——這是「k 路歸併」。
2. 暴力解：全部倒進陣列排序再建鏈，O(N log N)（N 為總節點數），但沒利用「每條已排序」。
3. 關鍵洞察（size-k 最小堆）：把 k 個頭節點放進最小堆，每次彈出最小的接到結果鏈尾，再把它的下一個節點推進堆。堆永遠最多 k 個，每次取最小 O(log k)。
4. 最優解：min-heap，O(N log k)。（另解：兩兩分治合併，同複雜度。）

import heapq

def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))   # i breaks val ties
    dummy = tail = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
    for (ListNode* node : lists) if (node) heap.push(node);
    ListNode dummy(0); ListNode* tail = &dummy;
    while (!heap.empty()) {
        ListNode* node = heap.top(); heap.pop();
        tail->next = node; tail = node;
        if (node->next) heap.push(node->next);
    }
    return dummy.next;
}

• 複雜度：時間 O(N log k)，空間 O(k)。
• 坑：① Python 的 heap 比較 tuple，但 ListNode 不可比較——所以塞一個唯一的 i 當第二排序鍵打破平手，否則 val 相同時會報錯；② 用 dummy 頭簡化接點；③ 別忘了只在 node.next 存在時才推回堆。

④ LC 56 — Merge Intervals

📋 題目：給定區間陣列 intervals（每個是 [start, end]），合併所有重疊的區間，回傳不重疊的區間集合。

範例：[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]；[[1,4],[4,5]] → [[1,5]]

🌐 EN — Given an array of intervals (each [start, end]), merge all overlapping intervals and return the non-overlapping set. Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]; [[1,4],[4,5]] → [[1,5]]

🧭 從讀題到解法

1. 拆解：要判斷哪些區間重疊——若順序是亂的，很難判。先排序，重疊的就會相鄰。
2. 關鍵洞察（按起點排序 + 掃描）：按 start 升序排序後，只需比較「當前區間的 start」和「結果裡最後一個區間的 end」：若 start <= 上一個 end，兩者重疊，把上一個的 end 更新成兩者較大；否則新開一個區間。
3. 為什麼排序後只需比相鄰？ 因為排序後，若當前區間和更早的某個重疊，必然也和「結果裡最後一個」重疊——傳遞性保證了只看最後一個就夠。
4. 最優解：排序 + 一次線性掃描。

def merge(intervals):
    intervals.sort(key=lambda x: x[0])             # sort by start
    res = []
    for start, end in intervals:
        if res and start <= res[-1][1]:            # overlaps the last merged
            res[-1][1] = max(res[-1][1], end)      # extend the end
        else:
            res.append([start, end])
    return res

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());      // sort by start
    vector<vector<int>> res;
    for (auto& iv : intervals) {
        if (!res.empty() && iv[0] <= res.back()[1])
            res.back()[1] = max(res.back()[1], iv[1]);
        else
            res.push_back(iv);
    }
    return res;
}

• 複雜度：時間 O(n log n)（排序主導），空間 O(n)。
• 坑：① 務必先按 start 排序；② 更新 end 要取 max——處理「巢狀區間」如 [1,10] 包住 [2,3] 的情況，不能直接覆寫；③ start <= end 還是 < 取決於題目是否把「剛好接邊」算重疊（本題算）。

⑤ LC 253 — Meeting Rooms II

📋 題目：給定一堆會議時間 intervals（[start, end]），回傳最少需要幾間會議室才能容納所有會議（同一時刻重疊的會議要分開的房間）。

範例：[[0,30],[5,10],[15,20]] → 2；[[7,10],[2,4]] → 1

🌐 EN — Given meeting times intervals ([start, end]), return the minimum number of meeting rooms required (meetings overlapping in time need separate rooms). Example: [[0,30],[5,10],[15,20]] → 2; [[7,10],[2,4]] → 1

🧭 從讀題到解法

1. 拆解：答案 = 任一時刻同時進行的會議數的最大值（peak concurrency）。
2. 暴力解：對每個時間點數有幾個會議在進行，太慢。
3. 關鍵洞察（排序 + 最小堆裝結束時間）：按 start 排序後逐一處理會議。用一個最小堆存「正在進行的會議的結束時間」。處理新會議時，若堆頂（最早結束的會議）<= 新會議的 start，代表那間房空出來了，彈出（複用房間）；然後把新會議的 end 推進堆。堆的大小 = 當下用了幾間房。
4. 最優解：因為每次最多彈一個、必推一個，堆大小不減，所以最後的堆大小 = 峰值並行數 = 答案。

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])             # by start
    heap = []                                      # end times of ongoing meetings
    for start, end in intervals:
        if heap and heap[0] <= start:              # earliest meeting freed a room
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end());      // by start
    priority_queue<int, vector<int>, greater<int>> heap;  // min-heap of end times
    for (auto& iv : intervals) {
        if (!heap.empty() && heap.top() <= iv[0]) heap.pop();
        heap.push(iv[1]);
    }
    return heap.size();
}

• 複雜度：時間 O(n log n)，空間 O(n)。
• 坑：① heap 存的是結束時間，堆頂是最早結束的會議；② 因為堆大小非遞減，最終大小就是答案，不必額外追蹤最大值；③ 邊界：end <= start 才算房間釋出（會議結束的瞬間另一場可開始，視題目定義）。另解：把所有 start 和 end 拆開各自排序，雙指針掃（chronological ordering），同樣 O(n log n)。

一張表記住全部

面試辨識口訣

• 看到「第 K 大/小、Top-K、合併 K 路、串流取最值」→ heap（size-k 最小堆是萬用模板）。
• 看到「頻率 Top-K」→ heap 或桶排序（桶排序 O(n) 最快）。
• 看到「合併 K 條排序結構」→ 最小堆做 k 路歸併。
• 看到「區間：重疊 / 合併 / 插入」→ 先按 start 排序再線性掃。
• 看到「區間：最多同時幾個 / 最少資源（會議室/月台）」→ 排序 + 最小堆裝結束時間（峰值並行）。

兩句話收尾:「要前 K 或合併 K 路，就用 heap;看到區間，先排序再掃。」 認出這兩個模式,這類題就從「想破頭」變成「套模板」。