「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)
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/225.html
您必须登录才能发表评论。