IT 面试题库

LeetCode 300 最长递增子序列(LIS):求数组的最长严格递增子序列长度,如何做到 O(n log n)?

高级编程题算法工程师动态规划LIS二分优化

题目

考察点:LIS 的二分优化——tails 数组(耐心排序)思想,以及状态定义的进阶(高级编程题)。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 65 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

思路:朴素 DP 为 O(n²);用『维护各长度递增子序列的最小结尾』可将决策降到二分,整体 O(n log n)。

要点(O(n²) 基础):

要点(O(n log n) 优化 · tails 数组):

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 数组存的不是真实子序列,只是长度与最小结尾,用于高效决策;要还原序列需额外记录前驱。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题