LeetCode 300.最长递增子序列-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目：给定一个整数数组，要求找到其中最长的递增子序列，返回这个子序列的长度。

解题思路

首先看题目，给定的是数组，并且是返回数组中的符合某个规律的结果。那么如果数组的长度为n，返回前n个符合此规律结果，如果数组为n-1，亦同。可以发现，n的结果可以根据前n-1的结果得到，符合此类规律的显然可以利用动态规划来解决问题。

那么回到本题，假设给定的数组为[1, 2, 3, 4]，并且最终的结果即为dp[i]（此处dp[i]的含义很重要，其所代表的是以i元素结尾的最长递增子序列的长度，那么很显然dp[0]=1，dp[1]则看nums[1]是否大于nums[0]，如果大于则dp[1] = dp[0] + 1，否则dp[1] = 1。dp[2]则是根据nums[0]和nums[1]的结果来确定，初始时很显然我们让dp[2]=1我们可以一步步更新dp[2]，首先看nums[2]和nums[0]的大小，如果大于则dp[2] = max(dp[2], dp[0] + 1) 否则同上，再看 nums[2]和 nums[1]大小，如果大于则dp[2] = max(dp[2], dp[1] + 1)。

总之，对于第i个元素，我们总是先初始化该位置的初始结果，之后根据前面符合条件的结果来更新此结果，可得代码如下：

public int lengthOfLIS(int[] nums) {
    int maxLen = 1;
    int[] dp = new int[nums.length];
    // dp[i] 以i元素结尾的最长递增子序列的长度
    dp[0] = 1;
    for(int i=1;i<nums.length;i++){
        dp[i] = 1;
        for(int j=0;j<i;j++){
            if(nums[j]<nums[i]){
                dp[i] = Math.max(dp[j]+1, dp[i]);
            }
        }
        maxLen = Math.max(dp[i], maxLen);
    }
    return maxLen;
}
复制代码

时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ 。

思路进阶（贪心+二分）

动态规划的时间复杂度还是较高的，如何优化这个时间复杂度呢？

需要注意的是，本题所关注的并不是最终的递增子序列是什么，而是最终正确子序列的长度。那我们是否可以遍历数组，将数组元素存入另一个数组中，存放过程始终保证数组的升序的，存入规则如下：

如果元素大于子数组中末尾元素值，则直接插入，子数组长度加一。
如果元素小于或者等于数组中末尾元素值，则利用二分将元素覆盖到合适的位置，覆盖过程始终保持数组递增。

上述思路就表明最终子数组中存储的一定是整个数组中较小的元素，这样子数组不一定是真正的递增子序列，但子数组长度是对的。可得代码如下：

public int lengthOfLIS4(int[] nums) {
    int[] arr = new int[nums.length+1];
    arr[1] = nums[0];
    int maxLen = 1;
    for(int i=1;i<nums.length;i++){
        if(nums[i]>arr[maxLen]){
            arr[++maxLen] = nums[i];
        } else {
            int l = 1, r = maxLen;
            while(l<r){
                int mid = (l + r) / 2;
                if(arr[mid]>=nums[i]){
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            arr[l] = nums[i];
        }
    }
    return maxLen;
}
复制代码

上诉代码可通过大部分用例，但存在一个问题，如果当前子数组中所有元素的大小都大于之后的待覆盖元素，则无法正确覆盖，即像[7, 8, 9, 1, 2, 3, 4, 5]这样的数组，最终会得到[0, 5, 8, 9, 0...]这样的答案，解决方法也很简单，判断一下最终待覆盖元素和覆盖元素的大小即可，如果待覆盖元素小于当前元素，则向后移动一位即可，可得代码如下：

public int lengthOfLIS5(int[] nums) {
    int[] arr = new int[nums.length+1];
    arr[1] = nums[0];
    int maxLen = 1;
    for(int i=1;i<nums.length;i++){
        if(nums[i]>arr[maxLen]){
            arr[++maxLen] = nums[i];
        } else {
            int l = 1, r = maxLen;
            while(l<r){
                int mid = (l + r) / 2;
                if(arr[mid]>=nums[i]){
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            if(arr[l]<nums[i]) l++;
            arr[l] = nums[i];
        }
    }
    return maxLen;
}
复制代码