#300
Medium
动态规划
Longest Increasing Subsequence
求最长严格递增子序列的长度。
求最长严格递增子序列长度。这题的优化版很经典，因为它不直接维护子序列本身，而是维护“每个长度下最小可能结尾”。
ArrayDPBinary Search
题目定位
它的经典入门解法是 DP，因为每个位置都在问“以我结尾的最长递增子序列是多少”；而进阶写法又能自然过渡到二分优化前沿状态。
关键观察
二分优化版并不真的存一条完整子序列，而是维护“每个长度下最小可能结尾”，这样才能给后续元素留下最大的接续空间。
目标复杂度
O(n log n) / O(n)
这题的解法思路怎么拆
1
维护 tails[i]，表示“长度为 i + 1 的递增子序列，最小可能的结尾值”。
2
对每个数字，在 tails 里二分找第一个大于等于它的位置。
3
用当前数字替换该位置，因为更小的结尾只会让后续更容易接上。
4
如果当前数字比所有 tails 都大，就把它追加到末尾，表示 LIS 长度增加了。
拿一个例子顺一遍
1
例如 nums = [10, 9, 2, 5, 3, 7, 101, 18]。
2
tails 的变化是 [10] -> [9] -> [2] -> [2, 5] -> [2, 3] -> [2, 3, 7] -> [2, 3, 7, 101] -> [2, 3, 7, 18]。
3
最终 tails 长度为 4，因此 LIS 长度就是 4。
参考实现
Pythonfrom bisect import bisect_left
def lengthOfLIS(nums: list[int]) -> int:
tails: list[int] = []
for value in nums:
index = bisect_left(tails, value)
if index == len(tails):
tails.append(value)
else:
tails[index] = value
return len(tails)
常见坑点
warning
把 subsequence 和连续子数组、子串混为一谈。
warning
把 tails 数组误当成真实答案序列，导致解释错误。
高频追问
如果面试官先要朴素解，你会怎样从 O(n^2) DP 讲到优化版？
如果要求输出具体子序列，还需要补哪些信息？
继续刷相关题
先把 动态规划 这个模式刷成体系，再去做更难变体。