高頻壓軸題庫#
這是一份「精選難題索引」。每一題只做一件事：幫你建立**「看到題目 ➡️ 想到該用哪個技巧」的條件反射。所以這裡不貼完整程式碼，只談三件事——考點（這題在考什麼）、最優解的一句話思路、以及為什麼到此為止**（也就是這題的下界，告訴你不必再硬找更快的解）。每題都連到 notes 中對應的章節，需要細節時再深入。
這些題目的共同特徵是：表面千變萬化，骨子裡都是少數幾個經典模型。練習的目標不是記住答案，而是練到能把陌生題「翻譯」成熟悉的模型。
總表：題目 ➡️ 考點 ➡️ 技巧 ➡️ 連結#
| 題目 | 考點 | 最優技巧 | 複雜度 | 連結 |
|---|---|---|---|---|
| 最長連續序列 ↗ | 雜湊集合 + 只從起點數 | Hash Set | O(n) | 雜湊應用 |
| 合併區間 ↗ | 排序後線性掃描 | Sort + Sweep | O(n log n) | 區間問題 |
| 稱球問題 | 資訊論下界 | 三分資訊量 | 3 次 | 複雜度的下界 |
| 天際線問題 ↗ | 掃描線 + 最大堆 | Sweep Line + Heap | O(n log n) | 區間問題、堆 |
| 最長回文子字串 ↗ | 線性回文擴展 | Manacher | O(n) | Manacher 最長回文 |
| 和為 k 的子陣列 ↗ | 前綴和差值配對 | Prefix Sum + Hash | O(n) | 子陣列與子序列、前綴和 |
| 搜尋結果摘要 | 多索引最小覆蓋視窗 | Sliding Window | O(n) | 滑動視窗、單詞搜尋 |
| 含括號計算器 ↗ | 邊讀邊依優先級求值 | 雙堆疊 / 遞迴 | O(n) | 堆疊與佇列 |
1. 最長連續序列（Longest Consecutive Sequence）#
- 考點：給一堆無序整數，求最長的連續整數序列長度。直覺會想到先排序，但排序就鎖死在
O(n log n)；真正的考點是用空間換時間，跳脫排序思維。 - 最優解一句話：把所有數丟進 Hash Set，只對「序列起點」（即
x-1不存在的x）往上連續數，每個數最多被走訪兩次。 - 複雜度：
O(n)時間、O(n)空間。 - 為何到此為止：至少要看過每個數一次，下界就是
O(n)，這個解已觸底。「只從起點數」是避免每個數都重複往上數、把總成本壓回線性的關鍵。 - 深入：雜湊應用
2. 合併區間 / 區間問題（Merge Intervals）#
- 考點：給一組
[start, end]區間，合併所有重疊者。這是一整類「區間問題」的母題（插入區間、區間交集、會議室數量都是它的變形）。 - 最優解一句話：依
start排序後線性掃描，當前區間與上一個重疊（cur.start <= prev.end）就合併，否則另起一段。 - 複雜度：
O(n log n)時間，瓶頸在排序。 - 為何到此為止：可以證明這類問題等價於排序——若存在線性解，就能用它在線性時間內排序，矛盾。所以
O(n log n)就是下界，不存在線性解，看到排序成本就該收手。 - 深入：區間問題
3. 稱球問題（12 顆球找一顆假球，3 次天平）#
- 考點：12 顆球中有一顆是假球（不知偏輕或偏重），只用天平 3 次找出它並判斷輕重。這題不是寫程式，而是考資訊論下界的思維。
- 最優解一句話：每次稱重有三種結果（左重 / 右重 / 平衡），等於一次取得 log₂3 bit 的資訊，三次最多分辨 3³ = 27 種情況。
- 複雜度：所需稱重次數的下界 = ⌈log₃(情況數)⌉。
- 為何到此為止：要分辨的情況共 24 種（12 顆球 × 輕或重），而 3 次能分辨 27 > 24，故 3 次足夠且必要（2 次只能分辨 9 種，不夠）。這正是「先算下界，知道最好能做到多好」的活教材。
- 深入：複雜度的下界
4. 天際線問題（The Skyline Problem）#
- 考點：給一堆矩形大樓
[left, right, height]，求其輪廓線（一連串關鍵轉折點）。考的是把二維幾何問題降成一維事件流的能力。 - 最優解一句話：用掃描線從左到右處理「樓的左右邊界」事件，維護一個最大堆記錄當前在線的高度，堆頂變化處就是輪廓的關鍵點。
- 複雜度：
O(n log n)，n 個事件各做一次堆操作。 - 為何到此為止：事件需依 x 座標排序、堆操作各
O(log n)，整體被排序與堆主導，O(n log n)即達到此類掃描線問題的下界。 - 深入：區間問題 與 堆
5. 最長回文子字串（Longest Palindromic Substring）#
- 考點：求字串中最長的回文子字串。樸素中心擴展是
O(n²)，考點在於消除重複擴展、把它壓到線性。 - 最優解一句話：Manacher 演算法——插入分隔符統一奇偶長度，維護當前最右回文邊界，用對稱性復用已知資訊，避免每個中心都從頭擴展。
- 複雜度：
O(n)時間、O(n)空間。 - 為何到此為止：至少要讀過整個字串，下界
O(n)；Manacher 讓每個位置的擴展量總和為線性，正好觸底。 - 深入：Manacher 最長回文
6. 和為 k 的子陣列（Subarray Sum Equals K）#
- 考點：求和恰為 k 的連續子陣列個數。暴力枚舉所有區間是
O(n²)，考點是把「區間和」轉成「兩個前綴和之差」。 - 最優解一句話：邊掃邊算前綴和
S，用雜湊表記錄每個前綴和出現次數；對當前S，累加count[S - k]，即可一遍找出所有合法區間。 - 複雜度：
O(n)時間、O(n)空間。 - 為何到此為止：必須讀過每個元素，下界
O(n)；前綴和把「找區間」化為「查表」，恰好線性完成。 - 深入：子陣列與子序列 與 前綴和
7. 搜尋結果摘要（含關鍵詞最多的視窗）#
- 考點：在一篇文章中找出同時涵蓋所有關鍵詞、且跨度最短的片段（即搜尋引擎的摘要 snippet）。考點是把「最小覆蓋區間」抽象成滑動視窗問題。
- 最優解一句話：先取得每個關鍵詞的出現位置索引，用滑動視窗右擴直到湊齊所有關鍵詞、再左縮逼出最短窗；多個有序索引以歸併方式推進。
- 複雜度：
O(n)時間（n 為各關鍵詞出現位置總數）。 - 為何到此為止：每個出現位置最多被左右指標各掃過一次，下界
O(n)，滑動視窗剛好線性。 - 深入：滑動視窗 與 單詞搜尋
8. 實作一個計算器（含括號的四則運算）#
- 考點：解析並計算含
+ - * /與括號的算式字串。考點是運算子優先級與括號的處理，陷阱是不能等讀完才算，得邊讀邊依優先級結算。 - 最優解一句話：用雙堆疊（運算元堆疊 + 運算子堆疊），遇到優先級不低於棧頂的運算子就先結算棧頂；括號遞迴或視為新的子作用域處理。
- 複雜度：
O(n)，每個 token 進出堆疊各一次。 - 為何到此為止：必須掃過整個輸入字串，下界
O(n)；雙堆疊一遍掃描即完成，無多餘工作。常見的坑：負號 / 一元運算、連除的整數截斷、空白字元。 - 深入：堆疊與佇列
回頭看這八題，你會發現面試的關鍵從來不是「背過這題」，而是能不能在陌生題目前，認出它其實是 Hash、排序掃描、掃描線 + 堆、前綴和、滑動視窗、雙堆疊裡的哪一個老朋友。把陌生題抽象成已知模型，才是真正可遷移的能力——這套思路的完整展開，見 演算法思維總綱。