題目與適用情境
給定整數陣列 nums，回傳任意一條最長嚴格遞增子序列。子序列保留原陣列中的相對順序，但元素 不必連續；「嚴格遞增」表示後一個值必須大於前一個值，相等值不能讓長度增加。有多個最長答案時 回傳任意一個，空陣列回傳空陣列。
輸入： [10, 9, 2, 5, 3, 7, 101, 18]
輸出： [2, 3, 7, 18]
索引遞增：2 < 4 < 5 < 7
數值遞增：2 < 3 < 7 < 18
長度：4採用面試限制：0 ≤ n ≤ 100,000，元素是 32 位元帶正負號整數，不可修改輸入陣列。這個規模 排除列舉所有子序列與平方級動態規劃作為最終方案。LeetCode 原題明確要求最長嚴格遞增子序列 長度，並追問 O(n log n)；2026 年公開面試準備資料仍同時講解平方級動態規劃與二分最佳化。 本文把輸出擴充為一條實際子序列，考察重點仍是同一個演算法不變量，不聲稱未經核實的公司歸屬或 面試頻率。
面試官考察重點
第一個訊號是能否精確定義狀態。平方級方案應讓 dp[i] 表示「必須以 nums[i] 結尾」的最長 遞增子序列長度。若只說「前 i 個元素的答案」，就遺失能否接上目前值所需的尾值資訊。
第二個訊號是從瓶頸推導最佳化。每個 i 向前掃描所有 j 會造成 O(n²)。更強的回答會換一個 狀態：對每個可達長度，只保留該長度下最小的尾值。尾值越小，未來越容易延伸；這些最小尾值嚴格 遞增，因此可以二分搜尋目前值應更新的位置。
第三個訊號是正確處理重複值。嚴格遞增要求找到第一個「大於或等於目前值」的位置，也就是 lower_bound 語意。相等值替換同一位置，不會延伸長度。若題目改為非遞減，才改成第一個「大於 目前值」的位置。
第四個訊號是知道 tails 不是答案本身。例如處理 [3, 5, 6, 2] 後，尾值陣列為 [2, 5, 6]；值遞增，但索引順序是 3, 1, 2，不是原陣列的子序列。回傳真實路徑必須另外保存 每個長度目前尾值的原陣列索引，以及每個元素的前驅索引。
最後一個訊號是能證明並驗證。候選人應說清最小尾值不變量、替換為何不遺失最佳長度、前驅鏈為何 合法，並用小規模 O(n²) 實作作為隨機測試 oracle，而不只跑一個範例。
回答前需要釐清的問題
- 嚴格遞增還是非遞減？ 本題嚴格遞增，重複值不能延長答案。若允許相等，需要改變二分邊界。
- 回傳長度還是實際序列？ 本題回傳一條實際序列，因此需要
previous與尾值索引；只回傳
長度可以把額外空間降到 O(L)，其中 L 是答案長度。
- 多個最佳答案如何選擇？ 任意一個都可接受。若要求字典序最小、索引序列最小或穩定選擇，
替換規則與證明都要增加限制。
- 輸入規模是多少？
n達十萬，需要O(n log n)；若n只有幾百，平方級動態規劃更容易
撰寫、解釋並擴充到計數問題。
- 輸入是否可能為空？ 可以，回傳
[]。這會影響重建前是否能讀取最後一個尾值索引。 - 能否修改輸入？ 不能。排序會破壞原索引順序，也會把子序列問題改成另一個問題。
- 整數是否會溢位？ 演算法只比較並複製值，不做加減乘除；32 位元整數不會因演算法運算溢位。
30 秒回答框架
「我為每個可達長度保存最小尾值。尾值有序，所以對每個數二分找到第一個大於等於它的位置：替換 該位置，或在末端追加。這個左邊界保證重複值不會延長嚴格遞增序列。尾值陣列不一定按原索引組成 答案，因此我同時保存尾索引和每個元素的前驅，最後反向重建。每個元素二分一次，時間 O(n log n)、空間 O(n)；測試涵蓋空陣列、重複值、遞減陣列和平方級隨機 oracle。」
分步深入解答
先寫容易證明的基準。令 dp[i] 為必須以 nums[i] 結尾的最長嚴格遞增子序列長度。任何長度 大於一的答案，其倒數第二個元素都來自某個 j < i 且 nums[j] < nums[i]：
dp[i] = 1 + max(dp[j])，其中 j < i 且 nums[j] < nums[i]
若不存在這樣的 j，則 dp[i] = 1
最終答案長度 = max(dp[i])這個定義同時給出正確性：任意合法前驅都能接上 nums[i]，而任何以 nums[i] 結尾的最佳序列 也必須從這些前驅之一轉移。問題在於每個 i 都掃描之前全部位置，總時間為 O(n²)。
最佳化時改為維護以下前綴不變量：處理完前 i 個元素後，tails[k] 是所有長度為 k + 1 的 嚴格遞增子序列中最小的可能尾值。若目前值為 x，查找第一個滿足 tails[k] ≥ x 的位置：
- 沒有該位置時，
x大於所有尾值，能把目前最長序列延長一位。 - 找到位置
k時，用x替換tails[k]。長度不變，但更小或相等的尾值不會減少未來選擇。 - 因為
tails嚴格遞增，位置可在O(log L)時間內找到。
以 [3, 5, 6, 2] 為例：前三步得到 [3]、[3, 5]、[3, 5, 6]；最後的 2 替換第一個 位置，得到 [2, 5, 6]。陣列長度仍正確，但 2 出現在原陣列末端，不能接到先前的 5, 6 之前。這正是不能直接回傳 tails 的反例。
重建需要兩組索引。tailsIndices[k] 保存目前實現最小尾值的原陣列位置；處理 nums[i] 並落在 位置 k 時，previous[i] 指向 tailsIndices[k - 1]。這個前驅在 i 之前，值也嚴格更小。 之後即使尾值被替換，已寫入的前驅關係不變。最後從最長長度的尾索引反向走即可。
export function longestIncreasingSubsequence(nums: number[]): number[] {
if (nums.length === 0) return []
const tails: number[] = []
const tailsIndices: number[] = []
const previous = new Array<number>(nums.length).fill(-1)
for (let index = 0; index < nums.length; index += 1) {
const value = nums[index]
let left = 0
let right = tails.length
while (left < right) {
const middle = left + Math.floor((right - left) / 2)
if (tails[middle] < value) left = middle + 1
else right = middle
}
const lengthIndex = left
if (lengthIndex > 0) {
previous[index] = tailsIndices[lengthIndex - 1]
}
if (lengthIndex === tails.length) {
tails.push(value)
tailsIndices.push(index)
} else {
tails[lengthIndex] = value
tailsIndices[lengthIndex] = index
}
}
const result = new Array<number>(tails.length)
let index = tailsIndices[tails.length - 1]
for (
let resultIndex = result.length - 1;
resultIndex >= 0;
resultIndex -= 1
) {
result[resultIndex] = nums[index]
index = previous[index]
}
return result
}正確性可分成三步。第一，tails 始終嚴格遞增：長度更長的遞增序列移除末項後，得到一個更短且 尾值更小的遞增序列。第二，二分替換保留每個長度的最小尾值；替換只改善可延伸性，不會虛構更長 序列。第三，每個 tailsIndices[k] 都對應一條真實長度為 k + 1 的鏈，前驅索引嚴格遞增、 前驅值嚴格更小。因此 tails.length 既不超過真實最佳長度，也不會漏掉任意真實最長序列逐項 迫使產生的長度；反向前驅鏈就是一個合法最佳答案。
每個元素執行一次長度至多為 L 的二分，總時間 O(n log L)，通常寫成上界 O(n log n)。 三個陣列合計 O(n) 空間，結果本身占 O(L)。演算法不排序輸入，也不依賴數值範圍。
測試應同時檢查長度、嚴格遞增與原索引順序：
const cases: Array<[number[], number]> = [
[[10, 9, 2, 5, 3, 7, 101, 18], 4],
[[0, 1, 0, 3, 2, 3], 4],
[[7, 7, 7, 7], 1],
[[5, 4, 3, 2, 1], 1],
[[], 0],
]
for (const [nums, expectedLength] of cases) {
const result = longestIncreasingSubsequence(nums)
if (result.length !== expectedLength) throw new Error("wrong length")
for (let i = 1; i < result.length; i += 1) {
if (result[i - 1] >= result[i]) throw new Error("not increasing")
}
}更強的驗證是隨機產生長度不超過 12 的小陣列，用 O(n²) 動態規劃求可信長度，再比較最佳化 結果；同時線性掃描原陣列，確認回傳值確實能依序比對。這能抓住重複值邊界、錯誤二分條件與錯誤 前驅。
高品質示範回答
「我先確認本題要求嚴格遞增並回傳一條實際序列。平方級方案是讓 dp[i] 表示以 nums[i] 結尾 的最長長度，再列舉所有更小的前驅。為了消除向前掃描，我會按長度保存最小可能尾值。
處理值 x 時，在尾值陣列中找第一個大於等於 x 的位置。若找不到，x 可以延長目前最長 序列；否則用 x 替換該位置，使相同長度擁有更容易延伸的尾值。嚴格遞增必須使用大於等於的 左邊界，所以重複值只替換，不增加長度。
尾值陣列只編碼每個長度的最佳結尾，不保證其中元素按原索引組成一條序列。為回傳實際答案，我用 tailsIndices[k] 記錄長度 k + 1 的目前尾索引。目前元素落在位置 k 時，把它的前驅設為 tailsIndices[k - 1]。掃描結束後從最長尾索引沿前驅反向填入結果。
不變量是：每個尾值都是該長度下可實現的最小尾值，每個尾索引都有一條真實前驅鏈。替換不會減少 既有長度，只會改善後續延伸條件；任何真實遞增子序列逐項掃描時，也會迫使尾值結構達到至少相同 長度，因此最終長度最佳。每個元素二分一次，時間 O(n log n)，索引與前驅占 O(n)。我會測試 空輸入、重複值、單調遞增遞減，並用小陣列的平方級解做隨機 oracle。」
常見錯誤
- 把子序列當成連續子陣列 → 滑動視窗無法跳過中間元素 → 用原索引遞增定義子序列。
- 先排序再求答案 → 排序破壞原相對順序 → 按輸入順序逐個更新狀態。
- 把
dp[i]定義成前綴最佳卻直接轉移 → 不知道最佳前綴的尾值能否接目前數 → **定義為
必須以 i 結尾。**
- 嚴格遞增時查找第一個大於目前值的位置 → 重複值會錯誤延長長度 → **查找第一個大於或等於
目前值的位置。**
- 直接回傳
tails→ 尾值可能來自逆序的原陣列索引 → 用尾索引與前驅鏈重建。 - 替換尾索引後回頭修改舊前驅 → 已建立的合法路徑被破壞 → 前驅寫入後保持不變。
- 只證明尾值有序 → 有序不足以證明長度最佳 → **證明「每個長度的最小可實現尾值」不變量
與上下界。**
- 把二分加插入寫成
O(log n)→ 陣列中間插入需要移動元素 → **這裡只做原地替換或末端
追加。**
- 只跑經典範例 → 重複值和前驅錯誤容易漏過 → 用全重複、全遞減、空輸入與隨機 oracle。
- 聲稱某公司高頻考察 → 公開題庫不能證明頻率或歸屬 → 只說明可核實的題目與演算法價值。
追問與應對
追問一：如果題目改為最長非遞減子序列呢？
相等值現在可以延長序列。二分邊界改為第一個嚴格大於 value 的位置，也就是右側插入點；前驅、 重建與複雜度不變。只改最終比較符號而不改二分，會在重複值上得到錯誤長度。
追問二：只回傳長度時能否減少空間？
可以刪除 tailsIndices 與 previous，只保留長度為 L 的最小尾值陣列，空間為 O(L)。 時間仍是 O(n log L)。若還要求回傳序列，輸出本身占 O(L)，而這份單遍重建方案需要每個輸入 位置的前驅資訊。
追問三：如何計算最長遞增子序列的數量？
最小尾值會合併同一長度的多條路徑，不能直接恢復計數。簡單方案維護 length[i] 與 count[i]： 列舉所有合法前驅，遇到更長路徑就覆寫長度並複製計數，遇到同長路徑就累加計數，時間 O(n²)。 大規模輸入可做座標壓縮，用 Fenwick Tree 或線段樹維護「最大長度及其計數」，但合併規則必須避免 重複計數。
追問四：輸入是只追加的資料流時怎麼辦？
目前最長長度可以線上維護：每到一個值就對 tails 做一次二分，單次 O(log L)。若要隨時輸出 一條實際序列，繼續保存索引與前驅。若資料流還會刪除舊元素，最小尾值可能依賴已刪除資料，原演算法 不能局部撤銷，需要更複雜的資料結構或離線分段處理。
追問五：如果每個元素有權重，要最大化遞增子序列總權重呢？
「最小尾值」不再足以代表狀態，因為相同尾值範圍可能對應不同累計權重。可按數值做座標壓縮，用 Fenwick Tree 或線段樹查詢所有較小值中的最大權重，再加上目前權重並更新目前位置。嚴格與非遞減的 查詢邊界仍須分別處理，複雜度為 O(n log n)。
追問六：要求字典序最小的最長答案時還能直接用這份程式碼嗎？
不能直接保證。目前替換規則只保證尾值最小，沒有在所有完整最佳路徑之間定義字典序穩定性。需要 先計算每個位置可作為多長前綴或後綴，再按能完成最佳長度的條件貪心選擇；若還要求最小索引序列， 比較規則又不同。回答前必須先釐清「字典序」比較的是值序列還是索引序列。