【lc刷题】300 最长上升子序列(DP&bisect)

47/300

最长上升子序列   给定一个无序的整数数组，找到其中最长上升子序列的长度。   示例:   输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明:   可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。#动态规划 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗? #二分查找   测试集： [4,10,4,3,8,9] [4,10,4,3,2,1] [10,9,2,5,3,7,101,18,19,20,30] [] [0] [10,10,10] [1,3,6,7,9,4,10,5,6]

动态规划类型，第四道：O(n*n)

class Solution: def lengthOfLIS(self, nums): if not nums: return 0 n = len(nums) memo = [1]*n for j in range(1, n): for i in range(j): if nums[j] > nums[i]: memo[j] = max(memo[i]+1,memo[j]) return max(memo)

【优化】使用二分查找：O(nlogn)

python中使用bisect二分查找插入位置

class Solution: def lengthOfLIS(self, nums): lst = [] for num in nums: p = bisect.bisect_left(lst, num) #找到此数字可能插入的位置 if p == len(lst): lst.append(num) #66的position是0 == len([]) or 77的position3 == len([0,10,20]) #[66] [0,10,20,77] else: lst[p] = num #9的postion是1 != len([0,10,20]) #[0,9,20] return len(lst)

举例nums = [4,10,4,5,2,1] num = 4, lst = [4] num = 10, lst = [4, 10] num = 4, lst = [4, 10] num = 5, lst = [4, 5] num = 2, lst = [2, 5] num = 1, lst = [1, 5] 不难看出，题目要求是长度，所以无碍。