Leetcode 300. 最长上升子序列

发表于
| 字数统计: 499 | 阅读时长 ≈ 2

题目描述

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

示例:

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, 3, 6, 7, 9, 4, 10, 5, 6]

首先从简单的情况考虑，数组中只有一个数[1]，此时无论怎样最长上升子序列长度都为1，记$f(1)=1$

如果增加了一个数变为[1, 3]，因为3大于2，所以此时最长上升子序列长度为2，$f(2)=f(1)+1$

但是如果增加的数是0，即数组为[1, 0]，此时最长上升子序列长度就成了1，因为0不大于之前的任何数，$f(2)=1$

以此类推，可以发现
$$f(N)=\max_{0<i<N} (f(i)+1),\quad if\ nums[N]>nums[i]$$
根据该转移方程，我们可以写出之前数组所对应状态：

1
2
nums = [1, 3, 6, 7, 9, 4, 10, 5, 6]
  dp = [1, 2, 3, 4, 5, 3,  6, 4, 5]

而最长上升子序列的长度就为$\max dp[i] = 6$

时间复杂度为$O(\frac{n*(n-1)}{2})=O(n^2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if nums == []: return 0
        # 第一个测试数据是空数组 = =
        dp = [1]
        for i in range(1, len(nums)):
            max_tmp = 0
            for j in range(len(dp)):
                if nums[i] > nums[j]:
                    max_tmp = max(max_tmp, dp[j])
            dp.append(max_tmp + 1)
        return max(dp)

执行用时 : 1760 ms, 在Longest Increasing Subsequence的Python3提交中击败了24.38% 的用户

内存消耗 : 12.9 MB, 在Longest Increasing Subsequence的Python3提交中击败了99.54% 的用户

咋这么慢捏