考察点:LIS 的二分优化——tails 数组(耐心排序)思想,以及状态定义的进阶(高级编程题)。
思路:朴素 DP 为 O(n²);用『维护各长度递增子序列的最小结尾』可将决策降到二分,整体 O(n log n)。
要点(O(n²) 基础):
dp[i] = 以 nums[i] 结尾的 LIS 长度,dp[i]=max(dp[j])+1(j<i 且 nums[j]<nums[i]);取全局 max。要点(O(n log n) 优化 · tails 数组):
tails[k] 表示『长度为 k+1 的递增子序列中,结尾元素的最小可能值』;tails 始终有序。x:用二分在 tails 中找第一个 ≥ x 的位置 pos 并替换 tails[pos]=x;若 x 比所有都大则追加。tails 的最终长度即 LIS 长度。import bisect
def lengthOfLIS(nums):
tails = []
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails): tails.append(x)
else: tails[pos] = x
return len(tails)
要点:tails 数组存的不是真实子序列,只是长度与最小结尾,用于高效决策;要还原序列需额外记录前驱。
题目与答案就在本页;收藏、批注和错题重练在应用内