Leetcode 300. 最长上升子序列 Longest Increasing Subsequence

目录

1. 动态规划 O(n^2)
2. 保存每个长度的序列的尾部元素

https://leetcode-cn.com/problems/longest-increasing-subsequence/

动态规划 O(n^2)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

保存每个长度的序列的尾部元素

tail[i] 代表长度 i + 1 的子序列的最后一个元素，最小可能是几。

理解对 tail 数组的更新：
如果当前数大于 tail 中最后一位，那么 tail 长度可以加一，新的最长序列的尾部元素自然就是当前的数

如果当前数不大于，虽然不能延伸最长序列，但是可能能降低前面的尾部元素的大小，可以找到前面第一个大于该数的尾部元素，把它替换掉。

第一种写法仍是 O(n^2)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        tail = [0] * len(nums)
        tail[0] = nums[0]
        max_l = 0
        for i in range(1, len(nums)):
            if nums[i] > tail[max_l]:
                tail[max_l+1] = nums[i]
                max_l += 1
            else:
                for j in range(max_l, -1, -1):
                    if nums[i] > tail[j]:
                        break
                if tail[j] < nums[i]:
                    tail[j+1] = nums[i]
                else:
                    tail[j] = nums[i]
        return max_l+1

第二种写法，加入二分搜索，时间复杂度降为 O（nlogn）

这里使用了 bisect 库中的二分搜索，（但是不能用二分插入，因为这里要替换） bisect 库介绍
其他使用 bisect 库的题目

import bisect
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        tail = [0] * len(nums)
        tail[0] = nums[0]
        max_l = 0
        for i in range(1, len(nums)):
            if nums[i] > tail[max_l]:
                tail[max_l+1] = nums[i]
                max_l += 1
            else:
                idx = bisect.bisect_left(tail[:max_l], nums[i]) # bisect 二分查找
                tail[idx] = nums[i]
        return max_l+1