题干与适用场景
给定整数数组 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)。
追问六：要求字典序最小的最长答案时还能直接使用这份代码吗？
不能直接保证。当前替换规则只保证尾值最小，没有在所有完整最优路径之间定义字典序稳定性。需要 先计算每个位置可作为多长前缀或后缀，再按可完成最优长度的条件贪心选择；若还要求最小索引序列， 比较规则又不同。回答前必须先澄清“字典序”比较的是值序列还是索引序列。