算法面试：如何用二分查找求最长递增子序列？

题干与适用场景

给定整数数组 nums，返回任意一条最长严格递增子序列。子序列保留原数组中的相对顺序，但元素不必连续；“严格递增”意味着后一个值必须大于前一个值，相等值不能让长度增加。存在多个最长答案时返回任意一个，空数组返回空数组。

text

输入： [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]：

text

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 之前，值也严格更小。以后即使尾值被替换，已经写入的前驱关系不变。最终从最长长度的尾索引反向走即可。

typescript

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)。算法不排序输入，也不依赖数值范围。

测试应同时检查长度、严格递增和原索引顺序：

typescript

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)。

追问六：要求字典序最小的最长答案时还能直接使用这份代码吗？

不能直接保证。当前替换规则只保证尾值最小，没有在所有完整最优路径之间定义字典序稳定性。需要先计算每个位置可作为多长前缀或后缀，再按可完成最优长度的条件贪心选择；若还要求最小索引序列，比较规则又不同。回答前必须先澄清“字典序”比较的是值序列还是索引序列。

题干与适用场景

text

输入： [10, 9, 2, 5, 3, 7, 101, 18]
输出： [2, 3, 7, 18]

索引递增：2 < 4 < 5 < 7
数值递增：2 < 3 < 7 < 18
长度：4

面试官考察点

回答前需要澄清的问题

严格递增还是非递减？ 本题严格递增，重复值不能延长答案。若允许相等，需要改变二分边界。
返回长度还是实际序列？ 本题返回一条实际序列，因此需要 previous 与尾值索引；只返回长度

可以把额外空间降到 O(L)，其中 L 是答案长度。

多个最优答案如何选择？ 任意一个都可接受。若要求字典序最小、索引序列最小或稳定选择，

替换规则和证明都要增加约束。

输入规模是多少？ n 达十万，需要 O(n log n)；若 n 只有几百，平方级动态规划更易

编写、解释和扩展到计数问题。

输入是否可能为空？ 可以，返回 []。这会影响重建前是否能读取最后一个尾值索引。
能否修改输入？ 不能。排序会破坏原索引顺序，也会把子序列问题改成另一个问题。
整数是否会溢出？ 算法只比较并复制值，不做加减乘除；32 位整数不会因算法运算溢出。

30 秒回答框架

分步骤深入解答

text

dp[i] = 1 + max(dp[j])，其中 j < i 且 nums[j] < nums[i]
若不存在这样的 j，则 dp[i] = 1
最终答案长度 = max(dp[i])

没有该位置时，x 大于所有尾值，能把当前最长序列延长一位。
找到位置 k 时，用 x 替换 tails[k]。长度不变，但更小或相等的尾值不会减少未来选择。
因为 tails 严格递增，位置可在 O(log L) 时间内找到。

typescript

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
}

测试应同时检查长度、严格递增和原索引顺序：

typescript

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")
  }
}

高质量示范回答

常见错误

把子序列当成连续子数组 → 滑动窗口无法跳过中间元素 → 用原索引递增定义子序列。
先排序再求答案 → 排序破坏原相对顺序 → 按输入顺序逐个更新状态。
把 dp[i] 定义成前缀最优却直接转移 → 不知道最优前缀的尾值能否接当前数 → **定义为

必须以 i 结尾。**

严格递增时查找第一个大于当前值的位置 → 重复值会错误扩展长度 → **查找第一个大于或等于

当前值的位置。**

直接返回 tails → 尾值可能来自逆序的原数组索引 → 用尾索引和前驱链重建。
替换尾索引后回头修改旧前驱 → 已建立的合法路径被破坏 → 前驱一经写入保持不变。
只证明尾值有序 → 有序不足以证明长度最优 → **证明“每个长度的最小可实现尾值”不变量

以及上下界。**

把二分加插入写成 O(log n) → 数组中间插入需要移动元素 → **这里只做原位替换或末尾

追加。**

只跑经典样例 → 重复值和前驱错误容易漏过 → 用全重复、全降序、空输入与随机 oracle。
声称某公司高频考察 → 公开题库不能证明频率或归属 → 只说明可核验的题目与算法价值。

题干

题干与适用场景

面试官考察点

回答前需要澄清的问题

30 秒回答框架

分步骤深入解答

高质量示范回答

常见错误

追问及应对

追问一：如果题目改为最长非递减子序列呢？

追问二：只返回长度时能否减少空间？

追问三：如何计算最长递增子序列的数量？

追问四：输入是只追加的数据流时怎么办？

追问五：如果每个元素有权重，要最大化递增子序列总权重呢？

追问六：要求字典序最小的最长答案时还能直接使用这份代码吗？

公开来源

Longest Increasing Subsequence (LIS): DP and Binary Search Interview Patterns (2025)

Longest Increasing Subsequence

Chapter 6: Dynamic Programming II

MIT ACM Reference 2008

bisect — Array bisection algorithm

Longest increasing subsequence

同类题目

题干

题干与适用场景

面试官考察点

回答前需要澄清的问题

30 秒回答框架

分步骤深入解答

高质量示范回答

常见错误

追问及应对

追问一：如果题目改为最长非递减子序列呢？

追问二：只返回长度时能否减少空间？

追问三：如何计算最长递增子序列的数量？

追问四：输入是只追加的数据流时怎么办？

追问五：如果每个元素有权重，要最大化递增子序列总权重呢？

追问六：要求字典序最小的最长答案时还能直接使用这份代码吗？

公开来源

Longest Increasing Subsequence (LIS): DP and Binary Search Interview Patterns (2025)

Longest Increasing Subsequence

Chapter 6: Dynamic Programming II

MIT ACM Reference 2008

bisect — Array bisection algorithm

Longest increasing subsequence

同类题目