目录

0300:最长递增子序列(★)

力扣第 300 题

题目

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7]子序列

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

提示:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶:

  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

相似问题:

分析

#1 dp

按前一元素选哪个即可递推。

1
2
3
4
5
6
7
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [1]*n
        for i in range(1,n):
            f[i] = 1+max([f[j] for j in range(i) if nums[j]<nums[i]],default=0)
        return max(f)

1000 ms

#2 dp+树状数组

  • 观察递推式,限制了一个维度 (nums[j]<nums[i]),求另一个维度(f[j])最值
  • 这种问题的一种常用方法是树状数组/线段树
  • 将一个维度看作区间范围,维护区间内的最值即可
  • 由于nums 元素可能为负,所以要归一处理后才能用树状数组
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class BIT:
    def __init__(self, n):
        self.n = n+1
        self.t = defaultdict(int)

    def update(self, i, x):
        i += 1
        while i<self.n:
            self.t[i] = max(self.t[i],x)
            i += i&(-i)

    def get(self, i):
        res, i = 0, i+1
        while i:
            res = max(res,self.t[i])
            i &= i-1
        return res

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        mi = min(nums)
        A = [x-mi for x in nums]
        tree = BIT(max(A))
        res = 0
        for x in A:
            f = 1+tree.get(x-1)
            tree.update(x,f)
            res = max(res,f)
        return res

101 ms

#3 dp+有序集合

  • 这种问题的另一种常用的方法是维护一种单调性
  • 假如 num[j1]<=nums[j2] 且 f[j1]>=f[j2],显然 j2 对之后的递推式来说是无用的,可以去掉
  • 那么维护有用的 <x=nums[j],y=f[j]> 的有序集合,x 和 y 都是递增的
  • 遍历到 nums[i] 时,在这个有序集合中二分查找最后一个满足 x<nums[i] 的元素 <x,y>,即得到 f[i]=1+y
  • 然后将所有不符合单调性的元素 <x,y> 去掉即可,类似单调栈
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        from sortedcontainers import SortedList
        sl = SortedList()
        res = 0
        for x in nums:
            pos = sl.bisect_left((x,))
            f = 1+sl[pos-1][1] if pos else 1
            while pos<len(sl) and sl[pos][1]<=f:
                sl.pop(pos)
            sl.add((x,f))
            res = max(res,f)
        return res

92 ms

#4 dp+单调数组

  • f 的范围更方便处理,还可以考虑反过来,维护 <x=f[j],y=nums[j]> 的有序集合
  • 遍历到 nums[i] 时,二分查找最后一个满足 y<nums[i] 的元素 <x,y>,得到 f[i]=1+x
  • 然后将所有不符合单调性的元素 <x,y> 去掉
  • 显然,这样的 k 最多一个,满足 x=f[i],y>=nums[i]
  • 因此 f 可以直接用数组维护,将 f[i] 位置改为 nums[i] 即可

解答

1
2
3
4
5
6
7
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        A = []
        for x in nums:
            pos = bisect_left(A,x)
            A[pos:pos+1] = [x]
        return len(A)

37 ms