0300：最长递增子序列（★）

2015-10-27 约 881 字预计阅读 2 分钟次阅读

力扣第 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
-10⁴ <= nums[i] <= 10⁴

进阶：

你能将算法的时间复杂度降低到 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

目录

0300：最长递增子序列（★）

题目

分析

#1 dp

#2 dp+树状数组

#3 dp+有序集合

#4 dp+单调数组

解答