最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/ 快手一面手撕算法

我们这篇文章的解法，结合了贪心思想 + 二分查找，非常精妙

算法解析

🎯 问题回顾

给定一个整数数组nums，找出其中严格递增的子序列的最大长度。

例如：nums = [10,9,2,5,3,7,101,18]
最长递增子序列可以是[2,3,7,18]或[2,3,7,101]，长度为4。

注意：子序列 ≠ 子数组（不要求连续）。

💡 核心思想：“用更小的尾巴，争取更长的未来”

我们不关心具体的 LIS 是什么，只关心它的长度。于是，我们可以维护一个数组tails，其含义是：

tails[i]表示：所有长度为i+1的递增子序列中，末尾元素的最小值。

✅ 为什么维护“最小末尾”？

• 末尾越小，后面就越容易接上更大的数，从而延长子序列。
• 这是一种贪心策略：在保证长度的前提下，让结尾尽可能小。

🔍 举个例子，手动模拟

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

我们逐个处理每个数字x，并更新tails：

✅ 最终len(tails) = 4，就是答案！

📌 注意：tails本身不一定是真实的 LIS（比如中间过程[2,3,7,18]是真的，但有些情况不是），但它长度一定等于 LIS 长度！

🔧 算法步骤详解

from bisect import bisect_left def lengthOfLIS(self, nums: List[int]) -> int: tails = [] # 初始化空数组 for x in nums: # 在 tails 中找第一个 >= x 的位置 pos = bisect_left(tails, x) if pos == len(tails): # x 比所有 tails 元素都大 → 可以延长 LIS tails.append(x) else: # 替换 tails[pos] 为 x，使该长度的末尾更小 tails[pos] = x return len(tails)

关键点解析：

1.bisect_left(tails, x)的作用

• 因为tails始终保持严格递增（证明见下文），所以可以用二分查找。
• bisect_left返回第一个≥ x的索引。

2.为什么tails是递增的？

• 假设存在i < j但tails[i] ≥ tails[j]。
• 那么长度为j+1的 LIS 末尾是tails[j]，而tails[j] ≤ tails[i]。
• 但我们完全可以从这个长度为j+1的序列中取前i+1个元素，得到一个长度为i+1、末尾 ≤tails[j] ≤ tails[i]的序列 —— 这与tails[i]是“长度 i+1 的最小末尾”矛盾。
• ✅ 所以tails必然严格递增！

正因为tails有序，才能用bisect_left！

3.替换操作不会影响已有的 LIS 长度

• 替换只是优化未来可能性，不改变当前最大长度。
• 例如：[2,5]→[2,3]，长度仍是2，但后续遇到4时，就能组成[2,3,4]，而[2,5]就不行。

⏱️ 复杂度分析

• 时间复杂度：

  • 遍历n个元素 → O(n)
  • 每次二分查找 → O(log L)，L 是当前 LIS 长度（≤ n）
  • 总计：O(n log n)

• 空间复杂度：

  • tails最多存 n 个元素 →O(n)

✅ 这是目前已知的 LIS 问题最优解法（仅求长度时）。

❗ 常见误区澄清

🧪 测试用例验证

nums = [0,1,0,3,2,3] → tails 变化： 0: [0] 1: [0,1] 0: [0,1] → 替换0? 不，bisect_left([0,1], 0)=0 → tails[0]=0（不变） 3: [0,1,3] 2: [0,1,2] 3: [0,1,2,3] → 长度4 ✅

✅ 总结：一句话记住这个算法

“维护一个递增的‘尾巴数组’，每次用新数字要么延长它，要么优化某个位置的尾巴，使其更小——这样未来的增长空间更大。”

这既是贪心（局部最优），又借助二分（高效查找），是算法设计中的经典范式。

跟着例子学算法

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

from bisect import bisect_left from typing import List class Solution: def lengthOfLIS(self, nums: List[int]) -> int: tails = [] # tails[i] 表示长度为 i+1 的递增子序列的最小末尾 for x in nums: pos = bisect_left(tails, x) # 👈 关键：找插入位置 if pos == len(tails): tails.append(x) # 👈 能延长 LIS else: tails[pos] = x # 👈 优化某个长度的末尾 return len(tails)

下面，我们逐行、逐元素地解释代码在每一步做了什么，并对应到你表格中的状态变化。

🔹 初始状态

tails = []

• tails为空，表示还没有任何递增子序列。

🔸 第1步：x = 10

pos = bisect_left(tails, 10) # tails=[], 所以 pos = 0 if pos == len(tails): # 0 == 0 → True tails.append(10) # tails = [10]

✅作用：第一个数，直接作为长度为1的LIS的末尾。
📊tails = [10]

🔸 第2步：x = 9

pos = bisect_left([10], 9) # 在 [10] 中找 ≥9 的位置 → index=0 if 0 == len([10])? → 0 == 1? → False else: tails[0] = 9 # tails = [9]

✅作用：9 比 10 小，不能延长（因为 9 < 10，但我们要严格递增，且当前最长只有1），但可以用 9替代长度为1的LIS的末尾，使其更小，为未来留空间。
📊tails = [9]

🔸 第3步：x = 2

pos = bisect_left([9], 2) # 2 < 9 → pos = 0 0 != 1 → 进入 else tails[0] = 2 # tails = [2]

✅作用：继续优化“长度为1”的LIS末尾，从9降到2，更小更好！
📊tails = [2]

🔸 第4步：x = 5

pos = bisect_left([2], 5) # 5 > 2 → 所有元素 < 5 → pos = len(tails) = 1 if 1 == 1 → True tails.append(5) # tails = [2, 5]

✅作用：5 比当前所有末尾都大（比2大），说明可以接在[2]后面，形成长度为2的递增子序列[2,5]。
📊tails = [2, 5]

🔸 第5步：x = 3

pos = bisect_left([2,5], 3) # # 2 < 3 → 继续；5 ≥ 3 → 停在 index=1 pos = 1 len(tails)=2 → 1 != 2 → else tails[1] = 3 # tails = [2, 3]

✅作用：3 不能延长到长度3（因为 3 < 5），但它可以替代长度为2的LIS的末尾：

• 原来长度2的末尾是5（如[2,5]）
• 现在可以用[2,3]，末尾更小，以后遇到4就能接上！
  📊tails = [2, 3]

🔸 第6步：x = 7

pos = bisect_left([2,3], 7) # 7 > 3 → pos = 2 len(tails)=2 → 2 == 2 → True tails.append(7) # tails = [2, 3, 7]

✅作用：7 比所有末尾都大，可以接在[2,3]后，形成长度为3的LIS[2,3,7]。
📊tails = [2, 3, 7]

🔸 第7步：x = 101

pos = bisect_left([2,3,7], 101) # 101 > 7 → pos = 3 3 == len(tails)=3 → True tails.append(101) # tails = [2, 3, 7, 101]

✅作用：继续延长，得到长度为4的LIS。
📊tails = [2, 3, 7, 101]

🔸 第8步：x = 18

pos = bisect_left([2,3,7,101], 18) # 2<18, 3<18, 7<18, 101≥18 → pos = 3 len(tails)=4 → 3 != 4 → else tails[3] = 18 # tails = [2, 3, 7, 18]

✅作用：18 不能形成长度5（因为 18 < 101，但前面最大末尾是101，而18比它小），
但它可以优化长度为4的LIS的末尾：

• 原来是[2,3,7,101]
• 现在可以是[2,3,7,18]，末尾更小，如果后面有19、20，就能继续延长！
  📊tails = [2, 3, 7, 18]

🎯 最终结果

return len(tails) # 4

✅ 返回4，正是 LIS 的长度。

🔑 核心代码逻辑总结

💡 为什么这样是对的？

• tails始终保持严格递增（可数学归纳法证明）
• 每次操作都不减少 LIS 长度，只可能增加或优化
• 最终len(tails)就是最长可能的长度

✅ 总结一句话

代码通过维护一个“各长度下最小末尾”的有序数组tails，利用二分查找高效决定：是延长序列，还是优化已有长度的结尾——从而在 O(n log n) 时间内求出 LIS 长度。