300. 最长递增子序列

难度中等1422收藏分享切换为英文接收动态反馈

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

进阶:

  • 你可以设计时间复杂度为 O(n2) 的解决方案吗?
  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

解答 :

  1. $O(n^2)$的方法:

    使用dp[i]表示[0,i]之间的最大子序列长度,根据最大子序列的定义来思考状态转移方程:

    dp[i]=max(dp[i],dp[j]+1 if j<i and nums[j]<nums[i])

    也就是一个循环遍历i,然后里面的循环遍历j,找到一个nums[i]小的然后更新;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
    _length=len(nums)
    if _length < 2:
    return _length
    dp=[1]*(_length+1)
    res=dp[0]
    for i in range(0,_length):
    for j in range(0,i):
    if nums[j]<nums[i]:
    dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])

    return res
  2. $O(NlogN)$的方法:

    贪心加二分,不是很好想;

    这里找的状态时tail[i],表示长度为i+1所有上升子序列的结尾最小值;这里的tail[i]时严格递增的,可以用反证法证明;

    这题就变成了维护tail这个数组,这个数组的长度就是我们要求的结果的长度;如何维护分为以下两步:

    • 扩充数组元素:

      如果遍历nums的时候这个 nums[i]>*(tail.end()),那么就把nums[i]添加到tail数组后面,此时相当于tail数组变长了一位;

    • 更新数组里面的元素:

      如果遍历nums的时候这个nums[i]<*(tail.end()),那么就要看tail数组里面第一个大于nums[i]的数,然后把它换成nums[i];

    例子解释:

    [9,2,3,6,7,4],初始化的时候表示长度的end=1,tail[end]=-1001,下面的[]表示tail数组

    [9] 遍历到9,9>tail[end],tail[end]=9

    [2] 遍历到2,2<tail[end],找到第一个大于2的,只有9,替换

    [2,3] 遍历到3,3>tail[end],添加进去

    [2,3,6] 同理

    [2,3,6,7] 同理

    [2,3,4,7] 遍历到4,4<tail[end],找到第一个大于4的,把它变小成4

    直观的来看,tail 数组越紧致,它越容易边长

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
    _length=len(nums)
    tail=[-1001]*(_length+1)
    end=1
    tail[end-1]=nums[0]
    for i in range(1,_length):
    if nums[i]>tail[end-1]:
    end=end+1
    tail[end-1]=nums[i]
    elif nums[i]<tail[end-1]:
    left=0
    right=end-1
    while left<right:
    mid=(left+right)>>1
    if tail[mid]<nums[i]:
    left=mid+1 # 中位数不是要找的数
    else:
    right=mid
    tail[left]=nums[i]
    return end