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路径搜索，最长路径的长度即是返回结果。对于每个节点，它能连接到的下一个节点满足以下两个条件：

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

根据以上条件进行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.

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

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

首先先看下基本思想：

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

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

首先将首元素4加入列表。 {4}
第二位9大于列表尾元素4，直接添加进列表。 {4，9}
第三位2小于列表尾元素9，从列表中找打第一个大于等于2的数字替换。 {2，9}（你对这一步也许会有疑问，暂且不论，后文阐述）
第四位5小于列表尾元素9，从列表中找打第一个大于等于5的数字替换。{2，5}
第五位3小于列表尾元素5，从列表中找打第一个大于等于3的数字替换。 {2，3}
第六位7大于列表尾元素3，直接添加进列表。{2，3，7}
第七位101大于列表尾元素7，直接添加进列表。{2，3，7，101}
第八位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，直接使用当前的这三个数字组成一个新的递增列表。

总结：

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

实现代码：

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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-300-longest-increasing-subsequence-解题思路分析/

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

发表评论取消回复

站内搜索

近期文章

功能

站内搜索

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

发表评论 取消回复

站内搜索

近期文章

标签

功能

站内搜索

发表评论取消回复