LeetCode - 300.Longest Increasing Subsequence

题目描述

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

1
2
3

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

1 2	Input: nums = [0,1,0,3,2,3] Output: 4

Example 3:

1 2	Input: nums = [7,7,7,7,7,7,7] Output: 1

Constraints:

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

解题方法

动态规划

定义一个 dp 数组，dp[i] 代表 nums 以 nums[i] 为结尾的最长递增子序列长度。

状态转移方程：

设 $j∈[0,i)$，即每一轮计算新的 $dp[i]$ 时，需要遍历 $[0,i)$ 列表区间
当 $nums[i] > nums[j]$ 时，表明 $nums[i]$ 可以接到递增序列的末尾，此时 $dp[i]=dp[j]+1$。
- $nums[i]<=nums[j]$ 时，跳过，因为此时 $nums[i]$ 不能够作为递增子序列的末尾。
- 转移方程：$dp[i]=max(dp[i],dp[j]+1),j∈[0,i),i∈[0,n]$
- 初始化 dp 为值为 1 的数组，因为每个元素都可以单独成为一个子序列。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

使用二分查找降低时间复杂度

将整个 dp 数组设计为一个排序列表，在需要计算最长递增子序列时，使用二分查找遍历 dp 数组，找到需要插入的下标位置，之后进行判断。

**初始化一个空的列表 sub**：
- 这个列表用于保存当前找到的最长递增子序列的末尾元素。
**遍历数组 nums**：
- 对于每个元素 num，使用二分查找来确定 num 在 sub 中的位置。
- 如果 num 大于 sub 中的所有元素（即 num 是新的最大值），就将其添加到 sub 的末尾。
- 如果 num 不是最大的，找到它在 sub 中应该插入的位置，并替换掉该位置的元素。这样可以保持 sub 的递增性质，并为后续元素提供更大的可能性。
返回 sub 的长度：
- sub 的长度即为最长严格递增子序列的长度。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = []  # 用于保存当前找到的最长递增子序列的末尾元素

        def binary_search(target):
            left, right = 0, len(sub)  # 初始化左右指针
            while left < right:
                mid = (left + right) // 2  # 计算中间位置
                if sub[mid] < target:  # 如果中间元素小于目标值
                    left = mid + 1  # 继续在右半部分查找
                else:
                    right = mid  # 继续在左半部分查找
            return left  # 返回插入位置

        for num in nums:  # 遍历数组 nums
            pos = binary_search(num)  # 查找当前元素的插入位置
            if pos == len(sub):  # 如果插入位置等于 sub 的长度，说明是新的最大值
                sub.append(num)  # 添加到 sub 的末尾
            else:
                sub[pos] = num  # 否则替换掉当前位置的元素
                
        return len(sub)  # 返回 sub 的长度，即最长递增子序列的长度

时间复杂度：$O(nlogn)$

空间复杂度：$O(n)$