「LeetCode每日一题」——300. 最长上升子序列

`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(nlogn) 吗?

`思路`

这道题也是动态规划的思路。

我们先定义状态，使用数组dp保存每步子问题的最优解。 dp[i] 代表从头元素开始，到第i个元素(包含i)的最长上升子序列的长度。

状态转移方程：

for i:0 -> n-1:
    dp[i] = Max{dp[j]}+1  j:0->i-1&&a[j]<a[i]

伪代码：

for i: 0->n-1:
  for j: 0->i-1:
        dp[i]

这里两层循环，时间复杂度为O(n^2)，空间复杂度O(n)

但是题目中有个进阶，要求我们找出O(nlogn)的时间复杂度的算法。

我们可以想想，在这里的伪代码：

for i: 0->n-1:
  for j: 0->i-1: 我们这第二层循环加速
        dp[i]

为什么我们可以在第二层循环加速，那是因为第一层遍历我们不能省略，只能在第二层想办法。

我们拿题目中的数组来举例子： [10,9,2,5,3,7,101,18]

如果我们维护一个数组L，进来一个新的元素，如果比较最后的元素大，那就加入数组，如果比最后元素小，那就替换。

 [10]              [10,9,2,5,3,7,101,18]
 [9]               [9,2,5,3,7,101,18]
 [2]               [5,3,7,101,18]
 [2,5]             [3,7,101,18]
 [2,3]             [7,101,18] 3和5比较，使用二分查找插入到5前面并替换5
 [2,3,7]           [101,18]
 [2,3,7,101]       [18]
 [2,3,7,18]        []   长度为4，这里有多种子序列，长度是一样的

这里使用了二分查找，第二层循环时间复杂度为O(logn)，总体时间复杂度为O(nlogn)。
代码见方案代码。

方案代码

动态规划:

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

二分查找：

import bisect
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        res = []
        for i in range(len(nums)):
            p = bisect.bisect_left(res,nums[i])
            if p == len(res):
                res.append(nums[i])
            else:
                res[p]=nums[i]
                
        return len(res)

「LeetCode每日一题」——300. 最长上升子序列

300. 最长上升子序列

题目

思路

方案代码

相关

相关推荐

`300. 最长上升子序列`

`题目`

`思路`