• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

最长递增子序列

开发技术 开发技术 3小时前 2次浏览

大家好,我是程序员学长。

今天我们来聊一聊最长递增子序列这个问题。

如果喜欢,记得点个关注哟~

问题描述

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

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

示例:

输入:nums = [2,1,6,3,5,4]

输出:3

解释:最长递增子序列是 [1,3,4],因此长度为 3。

分析问题

对于以第i个数字结尾的最长递增之序列的长度来说,它等于以第j个数字结尾的最长递增子序列的长度的最大值+1,其中 0<j<i,并且nums[j] < nums[i]。例如,对于以5结尾的最长递增子序列的长度,他等于以3结尾的最长递增子序列的长度+1。

最长递增子序列

所以,我们定义一个数组dp,其中dp[i]表示以第i个元素结尾的最长递增子序列的长度。则可以很容易的知道状态转移方程为:dp[i]=max(dp[j])+1,其中0<j<i 且 nums[j]<nums[i]。即考虑dp[0…i-1]中最长的递增子序列的后面添加一个元素nums[i],使得新生成的子序列满足递增的条件。

最后,整个数组的最长递增子序列的长度为数组dp中的最大值。

最长递增子序列

下面我们来看一下代码的实现。

def lengthOfLIS(nums):
    #如果数组为空,直接返回
    if not nums:
        return 0
    dp = []
    
    #从头遍历数组中的元素
    for i in range(len(nums)):
        dp.append(1)
        
        #在dp中寻找满足条件的最长递增子序列
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(lengthOfLIS([2,1,6,3,5,4]))

时间复杂度是O(n^2),其中n为数组nums的长度。因为对于数组nums的每个元素,我们都需要O(n)的时间去遍历dp中的元素。

空间复杂度是O(n),其中n为数组nums的长度。

优化

这里,我们也可以使用贪心的思想来解决。由于题目是求最长的递增子序列,要想使得递增子序列的长度足够长,就需要让序列上升的尽可能的慢,因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

我们维护一个数组d,其中d[i]表示长度为i的递增子序列的末尾元素的最小值,比如对于序列[2,1,6,3,5,4]来说,子序列1,3,51,3,4都是它的最长的递增子序列,则d[3]=4,因为4<5。

同时,我们也可以注意到数组d是单调递增的,即对于j<i ,那么d[j]<d[i]。我们可以使用反证法来证明,假设存在j<i时,d[j]>=d[i],我们考虑从长度为i的最长子序列的末尾删除i-j个元素,那么这个序列的长度变为j,且第j个元素x必然是小于d[i]的(因为是递增子序列,d[i]在x的后面,所以d[i]>x),又因为d[j]>d[i]的,所以可以得出x<d[j]的。那么我们就找到了一个长度为j的子序列,并且末尾元素比d[j]小,这与题设矛盾,从而可以证明数组d是单调递增的。

我们依次遍历数组中的元素,并更新数组d和len的值。如果nums[i] > d[len],则len=len+1,否则在数组d中,找到第一个比nums[i]小的数d[k],并更新d[k+1]=nums[i]。

最长递增子序列

def lengthOfLIS(nums):
    d = []
    #遍历数组中的元素
    for n in nums:
        #如果n比数组d的最后一个元素大,则加入数组中
        #否则,在d中寻找第一个小于n的元素的位置
        if not d or n > d[-1]:
            d.append(n)
        else:
            l = 0
            r = len(d) - 1
            k = r
            while l <= r:
                mid = (l + r) // 2
                if d[mid] >= n:
                    k = mid
                    r = mid - 1
                else:
                    l = mid + 1
            d[k] = n
    return len(d)

算法的时间复杂度是O(nlogn)。我们依次遍历数组nums,然后用数组中的元素去更新数组d,而更新数组d时,我们采用二分查找的方式来定位要更新的位置,所以时间复杂度是O(nlogn)。由于需要一个额外的数组d来保存,所以空间复杂度是O(n)。

进阶

下面我们把题目再修改一下,给定数组nums,设长度为n,输出nums的最长递增子序列。(如果有多个答案,请输出其中按数值进行比较的字典序最小的那个)。

示例:

输入:[1,2,8,6,4]

返回值:[1,2,4]

说明:其最长递增子序列有3个,(1,2,8)、(1,2,6)、(1,2,4)其中第三个按数值进行比较的字典序最小,故答案为(1,2,4)

由于题目要求输出最长递增子序列中数值最小的那个,所以我们要在上一题的基础上进行修改,这里引入一个数组maxlen,用来记录以元素nums[i]结尾的最长递增子序列的长度。

在得到数组maxlen和数组d之后,我们可以知道该序列的最长递增子序列的长度是len(d)。然后从后遍历数组maxlen,如果maxlen[i]=len(d),我们将对于元素返回结果res中,依次类推,直到遍历完成。

Tips:为什么要从后往前遍历数组maxlen呢?假设我们得到的maxlen为[1,2,3,3,3],最终的输出结果为res(字典序最小的最长递增子序列),那么res的最后一个元素在nums中位置为maxlen(i)==3对于的下标i,此时数组nums中有三个元素对应的最长递增子序列的长度为3,即nums[2]、nums[3]和nums[4],那到底是哪一个呢?如果是nums[2],那么nums[2] < nums[4] ,则maxlen[4]=4,与已知条件相悖,因此我们应该取nums[4]放在res的最后一个位置。所以需要从后先前遍历。

def lengthOfLIS(nums):
    #最长递增子序列
    d = []
    #记录以nums[i]结尾的最长递增子序列的长度
    maxlen = []
    #遍历数组中的元素
    for n in nums:
        #如果n比数组d的最后一个元素大,则加入数组中
        #否则,在d中寻找第一个小于n的元素的位置
        if not d or n > d[-1]:
            #更新最长递增子序列
            d.append(n)
            #更新以n为结尾元素的最长递增子序列
            maxlen.append(len(d))
        else:
            l = 0
            r = len(d) - 1
            k = r
            while l <= r:
                mid = (l + r) // 2
                if d[mid] >= n:
                    k = mid
                    r = mid - 1
                else:
                    l = mid + 1
            #更新最长递增子序列
            d[k] = n
            #更新以n为结尾元素的最长递增子序列
            maxlen.append(k+1)

    #求解按字典序最小的结果
    #此时我们知道最长长度为len(d),从后向前遍历maxLen,
    #遇到第一个maxLen[i]==len(d)的下标i处元素arr[i]即为所求
    lens = len(d)
    res = [0] * lens
    for i in range(len(maxlen)-1,-1,-1):
        if maxlen[i]==lens:
            res[lens-1]=nums[i]
            lens=lens-1
    return res

print(lengthOfLIS([1,2,8,6,4]))

算法的时间复杂度是O(nlogn),空间复杂度是O(n)。

最后

到此为止,我们就把这道题聊完了。

原创不易,各位觉得文章不错的话,不妨点赞、在看、转发三连走起!

你知道的越多,你的思维也就越开阔,我们下期再见。

最长递增子序列


程序员灯塔
转载请注明原文链接:最长递增子序列
喜欢 (0)