LEETCODE 300. Longest Increasing Subsequence 解题思路分析

题目大意:

最长上升子序列

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

示例:

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

说明:

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

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


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=300

解题思路分析:

解法一:DP动态规划(递归加记忆数组)

这道题使用递归方式解题会很简单。我们将数组中每个元素想象成为一个节点,然后以每个节点为起点向后做dfs路径搜索,最长路径的长度即是返回结果。对于每个节点,它能连接到的下一个节点满足以下两个条件:

  1. 下一个节点的index要大于当前节点。
  2. 下一个节点的值要大于当前节点的值。

根据以上条件进行dfs并无难度。我们从当前节点下标开始向后循环所有节点,当遇到大于当前节点时,说明找到一个递增节点,并dfs递归至该节点next。递归的返回值为从next节点到路径终点的长度,该长度再加上当前节点长度1为:从当前节点出发一条路径的长度。循环完所有符合条件的节点(大于当前节点)后,最长的路径长度即为当前递归的返回值。

另外我们还需要使用一个记忆数组来记录递归函数的状态(返回值)。因为递归函数中只有一个变量(当前下标index),因此,采用一个一维数组即可。

实现代码:

int[] memo; // 记忆数组
public int lengthOfLIS(int[] nums) {
    memo=new int[nums.length]; // 初始化记忆数组
    int max=0; // 全局最大值(最长路径)
    for(int i=0;i<nums.length;i++){ // 以数组中每一个数字为起点做dfs
        // 利用dfs返回值更新全局最大值
        max=Math.max(max, help(nums,i));
    }
    return max;
}
// nums:原始数组
// index:当前下标
// 返回值:当前下标开始到数组结尾区间的最长路径长度
int help(int[] nums, int index){
    // 如果当前是数组最后一位,那长度只能为1。
    if(index==nums.length-1) return 1;
    // 如果记忆数组中存在当前解,直接返回
    if(memo[index]>0) return memo[index];
    // 当前数值
    int num=nums[index];
    // 最大返回值。默认为当前节点自身,即长度为1
    int max=1;
    // 循环当前节点后的每一个节点
    for(int i=index+1;i<nums.length;i++){
        if(nums[i]>num){ // 找到每一个大于当前节点的节点
            // 递归至该节点,递归返回值为从第i个节点到数组末尾的最长路径的长度
            // 加一为当前节点长度
            int res=1+help(nums,i);
            // 用该长度更新当前递归中最大长度。
            max=Math.max(res,max);
        }
    }
    // 将最大长度保存至记忆数组
    memo[index]=max;
    return max; // 返回该最大长度
}

本题解法执行时间为20ms。

Runtime: 20 ms, faster than 19.39% of Java online submissions for Longest Increasing Subsequence.

Memory Usage: 37.7 MB, less than 37.81% of Java online submissions for Longest Increasing Subsequence.


解法二:贪心算法加二分查找

这道题的最优解是利用贪心结合二分查找的算法。如果你之前没接触过该贪心算法,那么本思路你可能会稍微难以理解,我会尽量使用浅显易懂的语言来描述出本解法的逻辑。

首先先看下基本思想:

  1. 我们维护一个升序列表,最终该升序列表的长度即是返回值。
  2. 使用贪心思想,向列表中添加元素时,每次尽量添加较小元素,这样才能使得后续加入更多较大元素,从而使得列表更长。
  3. 关键来了:首先向列表中添加数组中首元素,然后从数组第二位开始顺序循环每一个数字,如果当前数字大于列表中最后一个元素的话,可以将该元素直接添加到列表中。反之如果当前元素小于列表中最后一位时,我们采用二分方式找到列表中第一个大于等于当前数字的元素,并使用当前元素替换掉该元素(原理后文再阐述)。(该二分查找为我之前总结的所有二分套路中的第二条。LEETCODE常见算法之二分查找超详细白话讲解

举个例子,比如:[4,9,2,5,3,7,101,18]

  1. 首先将首元素4加入列表。 {4}
  2. 第二位9大于列表尾元素4,直接添加进列表。 {4,9}
  3. 第三位2小于列表尾元素9,从列表中找打第一个大于等于2的数字替换。 {2,9}(你对这一步也许会有疑问,暂且不论,后文阐述)
  4. 第四位5小于列表尾元素9,从列表中找打第一个大于等于5的数字替换。{2,5}
  5. 第五位3小于列表尾元素5,从列表中找打第一个大于等于3的数字替换。 {2,3}
  6. 第六位7大于列表尾元素3,直接添加进列表。{2,3,7}
  7. 第七位101大于列表尾元素7,直接添加进列表。{2,3,7,101}
  8. 第八位18小于列表尾元素101,从列表中找打第一个大于等于18的数字替换。 {2,3,7,18}

至此,列表元素个数定格为4,即本题返回结果。接下来我们复盘一下该解法,首先,如果当前数字大于列表尾元素时,将该元素直接加入列表的做法应该没有疑义。争议较大的操作出现在上述第3步,当时列表为{4,9},当前数字为2,此时,找到列表中第一个大于等于2的数字为4,进而我们使用数字2替代了4,将列表更新为{2,9}。这里你可能会有一个疑问,这样做是否正确?比如当原始数组为[4,9,2]时,我们找到的最长子序列不是{4,9},而是{2,9}。虽然数组本身不正确,但数组的长度没有任何问题,因为本题求解的是子序列长度,所以我们可以忽视序列中元素 的具体内容。接下来我们详细看下为什么该算法求出的长度是正确的?

还以上文为例,当数字2出现时,显然不能和当前列表{4,9}组成一个新递增序列,按照普通的想法,此时我们有2种选择,要么继续向后找比9大的数,要么,以2开头找一条新的路径。我们使用2替换4的目的就是同时兼顾上述两种选择,继续向后循环,当出现比9大的数字时,比如101,此时列表不论是{4,9,101}还是{2,9,101},这都不会影响列表的长度,只要我们知道9前面有一个数字小于它就是了,具体该数字是多少都不会改变9是当前列表中第二大数字的事实。另一方面,如果当前出现了小于9但是大于2的数字时,比如5,此时,我们会使用5替换掉9,相当于以2开头重新找新的一条路路线去了。此时数组会变为{2,5}。

再举个例子,比如当前列表为{2,9,101},当出现数字18时,列表会更新为为{2,18,101},此时这三个数字在原数组中的顺序应该是2,101,18,而列表{2,18,101}包含了2层意思,首先2和18的相对顺序是正确的,因此当大于18的数字出现时,我们会将101更新为大于18的数字,这样三个数字的顺序没有任何问题。另外,虽然101与18的顺序违背的原先数组中的顺序,但是18只是一个占位符,他并不影响101排在列表中第三位以及它是当前列表中最大数的事实。换句话说,如果今后我们找到了比101更大的数字时,直接添加到101后面不会影响结果的正确性。另外如果我们找到了一个大于18但小于101的数字时,我们还能轻松的踢掉101,直接使用当前的这三个数字组成一个新的递增列表。

总结:

  1. 无论列表中的数字如何添加与改变,列表中的所有元素始终保持了递增的状态。
  2. 在保持了递增的前提下,我们在不断使用较小值更新列表中的较大元素,从而使得列表长度可以达到最长。

实现代码:

public int lengthOfLIS(int[] nums) {
    if(nums.length==0) return 0; // 数组长度为0,返回0
    List<Integer> list = new ArrayList<>(); // 递增列表
    list.add(nums[0]); //添加首元素
    for(int i=1;i<nums.length;i++){ //循环每一个元素
        if(nums[i]>list.get(list.size()-1)){ //如果当前元素大于列表尾元素
            list.add(nums[i]); //直接添加
        }else if(nums[i]<list.get(list.size()-1)){
            //反之二分查找到第一个大于等于当前数字的元素
            int low=0,high=list.size()-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(list.get(mid)>=nums[i]){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
            //使用当前元素替换掉第一个大于等于它的元素
            list.set(low,nums[i]);
        }
    }
    return list.size();
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 72.99% of Java online submissions for Longest Increasing Subsequence.

Memory Usage: 39.6 MB, less than 9.39% of Java online submissions for Longest Increasing Subsequence.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-300-longest-increasing-subsequence-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。