每日一道算法之--最长上升子序列

动态规划二分查找贪心

Word count: 687Reading time: 3 min

 2020/03/18   Share

最长上升子序列

力扣第300题:https://leetcode-cn.com/problems/longest-increasing-subsequence/

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

示例:

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

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

1. 动态规划

一看到最字,首先想到的是动态规划和贪心算法。这道题动态规划还是挺好想的，循环两次遍历，这样子就能找到所有的情况，状态转移方程为：

if num[i] > num[j]:
    dp[i] = max(dp[i], dp[j] + 1)

代码如下:

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

1.1 复杂度分析

时间复杂度:O(n^2)，其中 n 为数组nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n^2)。

空间复杂度:需要额外使用长度为 n 的 dp 数组,所以空间复杂度为O(n)。

2. 贪心 + 二分查找

我一开始想到了用分治去处理这道题,但是因为分治太难去统计长度了,所以觉得不太行,就去看了一下官方题解。

代码如下：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        res = []
        for num in nums:
            if not res or num > res[-1]:
                res.append(num)
            else:
                l, r = 0, len(res) - 1
                index = r
                while l <= r:
                    mid = l + int((r -l) >> 1)
                    if res[mid] >= num:
                        index = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                res[index] = num
        return len(res)