面試題解析 第 51 頁，共 52 頁
瀏覽 OfferCC 面試題解析第 51 頁，查看解題思路、實作細節、追問與公開來源。
演算法面試題：找出陣列中的第 K 大元素
從完整排序與固定大小堆積推導至隨機化三向快速選擇，說清分割不變量、重複值處理、複雜度取捨，並用可執行測試驗證實作。
演算法面試：複製帶隨機指標的鏈結串列
從節點身分映射推導帶隨機指標鏈結串列的深拷貝，再掌握交錯節點的常數輔助空間最佳化、正確性不變量與原串列還原方法。
演算法面試：如何找出網路中的所有關鍵連線？
用發現時間和 low-link 值在線性時間內找出無向圖的全部橋，並證明嚴格判定條件，給出不受遞迴深度限制的迭代 DFS 實作。
演算法面試：如何每 K 個節點一組反轉鏈結串列？
用啞節點、完整分組預檢和區間內指標反轉解決 K 個一組反轉鏈結串列，並用迴圈不變量證明尾端不足 K 個節點時維持原序。
演算法面試：如何求直方圖中的最大矩形？
從左右第一個更矮柱推導直方圖最大矩形演算法，實作單次掃描的單調堆疊，並證明正確性與線性複雜度。
演算法面試：如何用動態規劃計算編輯距離？
從字串前綴推導編輯距離遞迴式，證明三種狀態轉移，並用 TypeScript 滾動陣列實作 O(mn) 時間、O(min(m, n)) 空間的解法。
演算法面試：如何用二分搜尋求最長遞增子序列？
從 O(n²) 動態規劃推導最小尾值不變量，再用二分搜尋、前驅索引與屬性測試實作並證明 O(n log n) 的最長遞增子序列演算法。
演算法面試：如何用雙向 BFS 解單字接龍？
把單字接龍建模為隱式無權圖，從最短序列要求推導 BFS，並實作每輪擴展較小前緣的雙向搜尋，附上嚴謹證明、複雜度核算與對抗測試。
演算法面試：如何實作 O(1) 的 LFU 快取？
用鍵索引、頻次桶、桶內雙向鏈結串列和最小頻次指標實作 LFU 快取，處理同頻 LRU 淘汰，並證明 get 與 put 的期望 O(1) 複雜度。
演算法面試：如何找出最小涵蓋子字串？
從二次列舉推導可變長度滑動視窗，以需求頻次、已滿足種類數與收縮不變量在線找出最短涵蓋區間，並用重複字元、無解輸入和隨機差分驗證 TypeScript 實作。
演算法面試：如何用雙指標解決接雨水？
從逐欄蓄水公式推導前後綴陣列與雙指標方案，用邊界不變量證明為什麼能安全移動較小一側，並以 O(n) 時間、O(1) 額外空間實作和驗證。
演算法面試：如何合併 K 個有序鏈結串列？
從候選首節點不變量推導 O(N log k) 解法，用大小不超過 k 的最小堆積完成實作與正確性證明，並比較掃描、依序合併、排序與分治方案。
演算法面試：如何實作 Dijkstra 最短路徑演算法？
用鄰接串列、最小堆惰性刪除與前驅陣列實作 Dijkstra，並證明貪心不變量，說清楚提前結束、複雜度和負權邊界。
演算法面試：如何實作並查集並維護連通分量？
從動態連通查詢推導並查集，用按大小合併和路徑折半實作 union、connected 與分量計數，並解釋正確性、均攤複雜度、測試方法和刪除限制。
演算法面試：如何用單調佇列求滑動視窗最大值？
從暴力掃描和 heap 方案推導單調雙端佇列，用支配關係、不變條件與攤銷分析證明 O(n) 時間，並給出實際只占 O(k) 空間的 TypeScript 環形佇列實作。
演算法面試：如何找出二元樹的最低共同祖先？
從路徑方案推導單次後序走訪，以子樹回傳值不變量證明最低共同祖先演算法，並處理重複值、缺少節點、極深樹與多次查詢等常見追問。
演算法面試：如何序列化與反序列化二元樹？
用帶空節點標記的前序走訪設計可逆編碼，證明解碼器如何剛好消耗一棵子樹，並處理格式錯誤、深樹邊界與替代格式。
演算法面試：如何求資料流的動態中位數？
用最大堆積維護較小的一半、最小堆積維護較大的一半，從不變量推導 O(log n) 插入與 O(1) 查詢，並涵蓋邊界、正確性證明及滑動視窗追問。
演算法面試：如何用二分搜尋目標值的首尾位置？
用 lower bound 與 upper bound 統一處理重複值、空陣列和目標不存在的情況，並透過半開區間不變量證明 O(log n) 解法正確。
演算法面試：如何合併重疊區間？
用排序加貪心掃描合併重疊閉區間，說明端點語意、正確性不變量、複雜度與輸入不可變，並涵蓋巢狀、鏈式重疊和串流處理等追問。
如何用拓撲排序解決課程表 II？
從課程相依關係推導 Kahn 拓撲排序，解釋建圖方向、零入度不變量、環偵測證明，並處理多解、重複邊與平行學期等追問。
如何實作支援插入、查找、前綴比對與刪除的 Trie？
從精確查找與前綴比對需求推導 Trie，實作不會破壞共用路徑的安全刪除，並驗證終止標記不變量、複雜度與對抗案例。
如何設計動態 Top-K 高頻項目的資料結構？
從讀寫比例推導動態 Top-K 的精確資料結構，提供可執行的頻次 bucket 實作、正確性不變量與複雜度，並說明記憶體受限時何時改用 Space-Saving 或 Count-Min Sketch。
如何實作執行緒安全的有界阻塞佇列？
用環形陣列、互斥鎖和兩個條件變數實作有界阻塞佇列，並從狀態不變量、線性化點、虛假喚醒和中斷語意證明多生產者、多消費者下的正確性。