题目描述

[EN | CN]

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

1
2
3
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 $O(n^2)$。

进阶:

你能将算法的时间复杂度降低到 $O(n \log n)$ 吗?

解法 1:DP

动规三部曲:

  1. 找动规矩阵:

    对于 dp[i],其表示 以第 i 个元素结尾 的最长上升子序列的长度。

  2. 找递推关系式:

    对于 dp[i],它等于从 dp[0]dp[i - 1] 中所有满足「最后一个值小于 num[i]」的结果中的最大值加一,表示之前的最长上升子序列加一。这一步的实现要求遍历从 0i - 1

  3. 找初始值:

    从 0 开始即可。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n^2)$,需要两层遍历;
  • 空间复杂度为 $O(n)$,需要保存 DP 数组。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
  • 执行用时:2000 ms,在所有 Python3 提交中击败了 7.07% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 7.89% 的用户。

解法 2:贪心 + 二分查找

参考官方题解。