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