LeetCode: L300 最长递增子序列

2021-09-25/2021-10-25 | 0 评论 | 1,090 浏览

题目: L300 最长递增子序列
来源: 力扣（LeetCode）
链接: https://leetcode-cn.com/problems/longest-increasing-subsequence
内容:
给你一个整数数组 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(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

答案1: 使用动态规划

怎样确定 dp 数组. 大家第一眼看题解的时候,都会看到: dp[i]=max(dp[i],dp[j]+1) 其实这里最重要的是要理解这个 dp[i]表示的含义.
这里实际的含义为: 以 nums[i]为结束字符的最长子串.
需要说明的点:

为什么这样能代表所有的子串?

这样标记子串后,怎么迭代. 也就是怎么才能动态起来. 也就是状态转移方程或者说是迭代函数

释义1: 为什么这样能代表所有的子串?

答案: 一个数组的如果存在一个最小子串(子数组).那一定这个最小子串存在的话.一定是以某一个元素作为结束元素的.因此把所有的元素都作为结束元素遍历一遍.并且把每一个元素作为结束元素的时候的子串长度都计算出来. 那一定能找出所有的最长子串`(虽然有的元素以它结束的时候并不是最长的)

释义2: 为什么可以进行迭代?

答案: 假设一个以 nums[i] 结束的最长子序列长度为dp[i] , 那后面紧接着加一个元素(可能是挨着的,也可能不是) 在dp[i]的基础上,如果这个新元素是大于nums[i]的.那新的dp[j] = dp[i] + 1 , 否则 dp[j]在最初始化的时候只能初始化为1.或者是保留之前dp[j]的值.(注: 之前的 dp[j]是之前另外的 dp[k]的基础上推演出来的),换句话说.反过来看.

当前条件:
知道了dp[i-1]及i-1之前的所有 dp 值,再强调一下: dp 数组中的位置 i存储的是以位置 i 的元素作为结束字符的可能的最长子序列的长度

计算 dp[i]:
最开始的时候 dp[i]的初始值是1.也就是位置i的元素单独作为一个独立子元素时长度. 然后与前面已经计算出来的 dp 值进行计算. 换句话说.这个nums[i]是否有可能与之前已经计算出的 dp 值的子串是否可以结合在一起. 如果 nums[j]< nums[i] ( 0 < j < i ) ,那 dp[i] 可以更新为dp[j]+1 ,否则不能拼到一起.只能保持原来的 dp[i] 值. 把所有的j迭代一遍后就可以确定出以i为结束元素的大序列中的最长子序列长度为 max{ dp[j]+1} ,where nums[j] < nums[i] and 0<j<i or 1

注

上述计算过程中, 是每次都知道了以前i-1个元素的每一个元素为结束元素的子序列 的最长长度. 那计算i位置时,如果 i 大于前端的i-1的任意一个元素. 那这个位置:i-1的元素可以拼到前面已经计算出的子序列后面.这样只可以临时得到一个可能的更长子序列. 然后取这些可能的更长的子序列中的最长的计为位置i 的(以位置 i 元素为结束的)最长子序列.

可能的错误思路

在想这个问题时,有可能陷入一个可能错误的思维陷阱里面.
假设知道了 dp[i-1] 的值为n (这里作为一般思考,并没有限定 dp[i-1]的值是一定以i-1位置的元素结束的) , 此时可能的dp[i]的值为: n或者n+1

因为这个 nums[i]的值可能会比原来的 dp[i-1]这么长的某子序列(这个子序列并不一定包含 nums[i-1])的最后一个元素大.那拼到一起则长度为n+1;
如果不比任意一个长度为 n 的子序列最后一个元素大那只可能取小于n的子序列长度拼到一起.最多也是保持原来的n的长度. 所以dp[i]最多是n+1;
但是需要确定到底是n还是n+1这个似乎就没有了思路.因为如果要确认就需要找到这个长度为 n 子序列.而且还需要把所有可能的n 长度的子序列都找出来.然后再判定原子序列的尾与当前元素比较. 如果要找出某个以元素位置 x的子序列是满足条件的长度为 n的一个最长子序列.那我就能进行比较. 换句话说,我还是要记录下以某个元素位置结束的最长子序列的大小,这样问题不又回到了上面的正确的解法的思路里面.
所以,这个比较泛泛的想法是不对的.不过在思考过程中给我们找到正确的解法提供了思路.

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null){
            return 0;
        }
        
        if(nums.length ==1 ){
            return 1;
        }

        int max = 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 1;i< nums.length;i++){
            dp[i]= 1;
            for(int j =0;j<i;j++){
                if(nums[i]<= nums[j]){
                    continue;
                }
                dp[i] = dp[i] < dp[j] +1 ? dp[j] +1 :dp[i];
            }
            max = max < dp[i] ? dp[i] : max;
        }
        return max;
    }
}

答案二

大家对于第二种解法的思路可能不是很理解. 听我分析下第一种思路与第二种思路之间存在的某种联系. 你就可以认为第二种思路是自然而然的了.

先说解法1. 动态规划是在顺序的遍历前 i-1个元素的 dp 值以及一直让 nums[i] 一直在与 nums[j]比较.
如下示例说明:

定义解释: dp[i]中存储的是以位置 i元素为结尾的最长子序列的长度.

nums[0] , nums[1] , nums[2] , nums[3], .... , nums[j] , nums[i]
dp[0]    ,  dp[1]   , dp[2]   , dp[3], .... ,   dp[j]    ,dp[i]

无序列表最开始的时候. 我们是需要一一让 nums[i] 与 nums[j] 比较. 然后找到比 nums[i]的小那些j值.
如果哪些位置的 nums 值(即数组中的元素的值)是小于 nums[i]这个可以快速确定的话. 那我们就可以把原来的 o(n^2)的代码中的里面一层的n优化为logn
现在这里有 dp 数组的索引 (1-> j) 以及对应于每个位置对于的子序列长度n以及,当前记录的子序列的结束元素(即位置 j对应的元素值nums[j]) , 换句话说,我们现在一个mapping 序列: j -> L,Vtail;

用示意图表示为:

=====================================================
尾值:___11__+__12__+__13__+__8__+__7__+__14__+__6__+__18__+
----+------+------+------+---------------------------------------
长度:___01__+__02__|__03__|__01__+__01__+__04__+  ...
位置:___d1__|__d2__|__d3__|__d4__|__d5__|__d6__|  ...
=====================================================
备注:
尾值行: 实际就是原数组 nums[]
长度行: 就是 dp 数组的位置 i 的最长子串值
位置就是 dp 的索引.

如上我们现在已经来到了位置为6的地方,我们已经计算出了 dp 数组.
每个j值对应一个子串长度Lj
第个j值对应一个尾值.即当前元素 nums[j],也就是以位置 i 的位置为结束的最长子串的结尾值.
我们想找到最合适的j,把当前的位置i的元素nums[i]插入到子串中,使子串变长.
现在是有 j -> Lj ,以及 Tail_J. 如果能重新组织这三个元素的关系. 比如用 Lj来找 j和tail_j.
我们把上面的那个数组重新组织排列 , 把所有的 L值进行重新排列.我们会得到一个单调不减数组
L1 ,L2, L3, .... , Lj , 为什么说是单调不减数组. 是因为不同的 dp[j]的值可能会相同.换句话说.有可能有多个 j 对应的 dp 数组的 dp[j]值相同.

但是可以证明:L值越大的Vtail 的最小值一定是比小于此 L 值的 Lx的 Vtail 值大. 这个证明方法与上面说的一样,就不赘述.(反证法)

这样:
L 值相同的 L 项,可以合并.并且只留一个 Vtail 最小的那一个. (比如上面的例子中的 L1,L2,L3,假设他们的长度一样.我们只需要留一个 VTAIL 最小的那个. 因为只有这样,我们在拼 i 位置部分的 nums[i]值时,才最有可能拼出最小的,最长的最长子序列.

再回到上面的例子:

我们有了一个 dp[i]数组
我们有了相应的 j -> L , Vtail 的关系.
我们再把这个关系如果重新组织成: L -> j , Vtail
然后再合并 L相等的.
我们最后在拼 nums[i]的时候, 我们并不关心 j 值是哪个. 我们只关系这个 j 值对应的 L 和 vtail 是多少.
因此, 如果反过来表示的数组. 有 L-> Vtail 的时候,我们并不关心这上 L 是在哪一个 j 上产生的.
这样我们得到了:
L1, L2, L3 , L4
T1, T2,T3 , T4
L1 -> L4 ,长度依次递增.
并且也证明了:长度递增时,T1 -> T4也是依次递增.
那我在处理 nums[i]的时候. 采用贪心原则.
我可以把 nums[i] 与 L作为下标,T作为值的数组进行快速比较的时候,我就能确定把 nums[i]放到一个最合适的位置,使原来的某个 L 长度能+1.
如果是 L3长度加1.那他可能与 L4相等. 且 L3的新尾数是小于 L4的.因此. 这个 L4的尾数应该淘汰掉. => 几步合一步实际就是直接更新 L4的 Vtail 为 nums[i].
如果这个数大于了 L4的 tail.那只最适合放到 L4上.更新 L4为一个新的 L 长度.此时右边没有.可能直接把新的 L 长度作为新的最长子串.且 tail 为 nums[i].这样. 就可以一直找到最长的 tail 了.
在查找的过程中使用二分查找.可以降低复杂度到logn

算法为:

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null){
            return 0;
        }

        if(nums.length ==1 ){
            return 1;
        }

        int[]  l = new int[nums.length+1];
        int maxSubLen = 1;
        l[1] = nums[0];
        for (int i = 1;i< nums.length;i++){
            int left = 1;
            int right = maxSubLen;
            // find the max number that less nums[i]
            int nTail = nums[i];

            if(l[right]<nTail){
                maxSubLen +=1;
                l[maxSubLen] = nTail;
                continue;
            }
            if(l[1]>nTail){
                l[1] = nTail;
                continue;
            }
            while(left < right){
                int mid = left + ( (right - left) / 2 ) ;

                if(nTail < l[mid]){
                    if(mid > left+1){
                        right = mid;
                        continue;
                    }
                    // break condition: mid < nums[left]
                    l[left+1] = nTail;
                    break;
                }else if(nTail > l[mid]){
                    if(mid < right-1){
                        left = mid;
                        continue;
                    }
                    // break condition: 
                    l[mid+1] = nTail;
                    break;
                }
                break;
            }
        }
        return maxSubLen;
    }
}

优化后的算法:

/*
=====================================================
尾值:___11__+__12__+__13__+__8__+__7__+__14__+__6__+__18__+
----+------+------+------+---------------------------------------
长度:___01__+__02__|__03__|__01__+__01__+__04__+  ...
位置:___d1__|__d2__|__d3__|__d4__|__d5__|__d6__|  ...
=====================================================
备注:
尾值行: 实际就是原数组 nums[]
长度行: 就是 dp 数组的位置 i 的最长子串值
位置就是 dp 的索引.
*/
class Solution {

    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0){return 0;}
        if(nums.length == 1){ return 1;}

        // 从1开始用. 0 不使用
        int[] ldp = new int[nums.length+1];
        ldp[1] = nums[0];
        int left = 1;
        int right = 1;
        for(int i=1;i<nums.length;i++){
            int index = find(ldp,left,right,nums[i]);
            ldp[index] = nums[i];
            if(index == right+1){
                right++;
            }
            ldp[index] = nums[i];
        }
        return right;
    }

    // 寻找一个索引位置k ,使得 index <=k 的地方的元素都小于给你写的vTail
    // 更准确的说是查找 位置k 使得: a[k-1] < vTail ( 如果k-1这个位置存在的话 )且 vTail <= a[k]
    int find(int[] a , int left , int right , int vTail){
        while(left<=right){
            int mid = left + (right - left)/2;
            if( vTail > a[mid]){
                left = mid+1;
            }else if(vTail < a[mid]){
                right = mid-1;
            }else{
                return mid;
            }
        }
        return left;
    }
}

RBA的技术分享