解题结果
题目、答案、思路和复杂度

题目描述

给定整数数组 `nums`,请返回最长严格递增子序列的长度。 示例: 输入:`[10,9,2,5,3,7,101,18]` 输出:`4`

答案代码

def longest_increasing_subsequence(nums): tails = [] for num in nums: left, right = 0, len(tails) while left < right: mid = (left + right) // 2 if tails[mid] < num: left = mid + 1 else: right = mid if left == len(tails): tails.append(num) else: tails[left] = num return len(tails)

解题思路

第一步先说明朴素动态规划可以做,但时间复杂度较高。
第二步引入 `tails` 数组,维护不同长度递增子序列的最小结尾。
第三步利用二分查找替换位置,把时间复杂度降到 `O(n log n)`。

复杂度

时间复杂度O(n log n)
空间复杂度O(n)
当前语言Python