8°

力扣300——最长上升子序列

这道题主要涉及动态规划,优化时可以考虑贪心算法和二分查找。

原题

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
  • 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解题

暴力法

这也是最基础的想法,利用递归,从每一个数开始,一个一个寻找,只要比选中的标准大,那么就以新的数为起点,继续找。全部找完后,找出最长的序列即可。

也看一下代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 递归查询
        return recursiveSearch(nums, Integer.MIN_VALUE, 0);
    }
public int recursiveSearch(int[] nums, int standard, int index) {
    if (nums.length == index) {
        return 0;
    }
    
    // 如果包含当前index的数字,其递增长度
    int tokenLength = 0;
    if (nums[index] > standard) {
        tokenLength = 1 + recursiveSearch(nums, nums[index], index + 1);
    }

    // 如果不包含当前index的数字,其递增长度
    int notTokenLength = recursiveSearch(nums, standard, index + 1);

    // 返回较大的那个值
    return tokenLength > notTokenLength ? tokenLength : notTokenLength;
}

}

提交之后报超出时间限制,这个也是预料到的,那么我们优化一下。

记录中间结果

仔细分析一下上面的暴力解法,假设 nums 是:[10,9,2,5,3,7,101,18],那么从 7 到 101 这个查找,在2、5、3的时候,都曾经查找过一遍。

那么针对这种重复查找的情况,我们可以用一个二维数组,记录一下中间结果,这样就可以达到优化的效果。比如用int[][] result标记为记录中间结果的数组,那么result[i][j]就代表着从 nums[i - 1] 开始,无论包含还是不包含 nums[j] 的最大递增序列长度。这样就能保证不再出现重复计算的情况了。

让我们看看代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 记录已经计算过的结果
        int result[][] = new int[nums.length + 1][nums.length];
        for (int i = 0; i < nums.length + 1; i++) {
            for (int j = 0; j < nums.length; j++) {
                result[i][j] = -1;
            }
        }
        // 递归查询
        return recursiveSearch(nums, -1, 0, result);
    }
public int recursiveSearch(int[] nums, int preIndex, int index, int[][] result) {
    if (nums.length == index) {
        return 0;
    }

    // 如果已经赋值,说明计算过,因此直接返回
    if (result[preIndex + 1][index] &gt; -1) {
        return result[preIndex + 1][index];
    }

    // 如果包含当前index的数字,其递增序列最大长度
    int tokenLength = 0;
    if (preIndex &lt; 0 || nums[index] &gt; nums[preIndex]) {
        tokenLength = 1 + recursiveSearch(nums, index, index + 1, result);
    }

    // 如果不包含当前index的数字,其递增序列最大长度
    int notTokenLength = recursiveSearch(nums, preIndex, index + 1, result);

    // 返回较大的那个值
    result[preIndex + 1][index] = tokenLength &gt; notTokenLength ? tokenLength : notTokenLength;
    return result[preIndex + 1][index];
}

}

提交OK,但是结果感人,几乎是最慢的了,无论时间还是空间上,都只打败了`5%`左右的用户,那就继续优化。

### 动态规划

假设我知道了从 nums[0] 到 nums[i] 的最大递增序列长度,那么针对 nums[i + 1],我只要去跟前面的所有数比较一下,找出前面所有数中比 nums[i + 1] 小的数字中最大的递增子序列,再加1就是 nums[i + 1] 对应的最大递增子序列。

这样我只要再记录一个最大值,就可以求出整个数组的最大递增序列了。

让我们看看代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
    // 动态规划,之前几个数字中,有几个比当前数小的,不断更新

    // 存储中间结果
    int[] dp = new int[nums.length];
    // 最大值,因为数组中至少有一个,所以最小是1
    int max = 1;
            // 遍历
    for (int i = 0; i &lt; dp.length; i++) {
        // 当前下标i的最大递增序列长度
        int currentMax = 0;
        for (int j = 0; j &lt; i; j++) {
            // 如果nums[i]比nums[j]大,那么nums[i]可以加在nums[j]后面,继续构成一个递增序列
            if (nums[i] &gt; nums[j]) {
                currentMax = Math.max(currentMax, dp[j]);
            }
        }

        // 加上当前的数
        dp[i] = currentMax + 1;

        max = Math.max(dp[i], max);
    }

    return max;
}

}

提交OK,执行用时:9 ms,只战胜了75.15%的 java 提交,看来还是可以继续优化的。

贪心算法 + 二分查找

贪心算法意味着不需要是最完美的结果,只要针对当前是有效的,就可以了。

我们之前在构造递增序列的时候,其实是在不断根据之前的值进行更新的,并且十分准确。但其实并不需要如此,只要保证序列中每个数都相对较小,就可以得出最终的最大长度。

还是以[10,9,2,5,3,7,101,18,4,8,6,12]举例:

  1. 从10到2,都是无法构成的,因为每一个都比之前的小。
  2. 当以最小的2作为起点后,2,52,3都是可以作为递增序列,但明显感觉2,3更合适,因为3更小。
  3. 因为7大于3,因此递增序列增长为2,3,7
  4. 因为101也大于7,因此递增序列增长为2,3,7,101
  5. 因为18小于101,但是大于7,因此我们可以用18替换101,因为18更小,序列更新为2,3,7,18
  6. 此时遇到4,4大于3但是小于7,我们可以用它替换7,虽然此时新的序列2,3,4,18并不是真正的结果,但首先长度上没有问题,其次如果出现新的可以排在最后的数,一定是大于4的,因为要先大于现在的最大值18。序列更新为2,3,4,18
  7. 同理,8大于4小于18,替换18,此时新的序列2,3,4,8,这样是不是大家开始懂得了这个规律。
  8. 遇到6之后,更新为2,3,4,6
  9. 遇到12后,更新为2,3,4,6,12

这样也就求出了最终的结果。

结合一下题目说明里提到的O(nlogn),那么就可以想到二分查找,运用到这里也就是找到当前数合适的位置。

接下来让我们看看代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
    // 贪心 + 二分查找

    // 一个空数组,用来存储最长递增序列
    int[] result = new int[nums.length];
    result[0] = nums[0];
    // 空数组的长度
    int resultLength = 1;
    // 遍历
    for (int i = 1; i &lt; nums.length; i++) {
        int num = nums[i];
        // 如果num比当前最大数大,则直接加在末尾
        if (num &gt; result[resultLength - 1]) {
            result[resultLength] = num;
            resultLength++;
            continue;
        }
        // 如果和最大数相等,直接跳过
        if (num == result[resultLength - 1]) {
            continue;
        }

        // num比最大值小,则找出其应该存在的位置
        int shouldIndex = Arrays.binarySearch(result, 0, resultLength, num);
        if (shouldIndex &lt; 0) {
            shouldIndex = -(shouldIndex + 1);
        }
        // 更新,此时虽然得出的result不一定是真正最后的结果,但首先其resultLength不会变,之后就算resultLength变大,也是相对正确的结果
        // 这里的更新,只是为了让result数组中每个位置上的数,是一个相对小的数字
        result[shouldIndex] = num;
    }

    return resultLength;
}

}

提交OK,执行用时:2 ms,差不多了。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题目用动态规划其实就已经能解决了,但为了优化,还需要用到贪心算法和二分查找。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

本文转载自博客园,原文链接:https://www.cnblogs.com/death00/p/12189579.html

全部评论: 0

    我有话说: