Leetcode300.最长上升子序列

Leetcode300.最长上升子序列

1.题目描述

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

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

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

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

2.解答

本来一开始我想要使用暴力方法先进行一些求解,因为我看到了题目中的时间复杂度为O(n*n),编码完成之后可以通过常规的测试用例,但是对于一些比较刁钻的没有考虑在内,如果出现了中途的上升下降,又下降,例如测试用例:[2,7,5,3,4]处理起来很棘手,甚至需要三层循环,接下来还是使用这道题目的标准解法---动态规划来实现,就像树的问题几乎都可以使用递归一样,这种子序列或者子串问题大多都可以使用动态规划来解决

直接上代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        //初始条件判断
        if(nums.length == 0 || nums == null)    return 0;
        //创建动规数组并进行初始化
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        int res = 0;
        for(int i = 0;i < nums.length;i++){
            for(int j = 0;j < i;j++){
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i],dp[j]+1);
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

dp[i]表示nums数组的前i个元素中的最长上升子序列多大,那么递归关系就是对i之前的元素进行遍历:0<j<i,如果满足 nums[i] > nums[j],那么更新dp[i]


优化
上面使用基本的动规解决,时间复杂度为O(n*n),那么我们是否可以对时间复杂度进行优化呢?
这里用到了贪婪的思想还有二分查找

实现代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        if(length <= 1) return length;
        int[] tail=  new int[length];
        tail[0] = nums[0];
        int end = 0;
        for(int i = 1;i < length;i++){
            if(nums[i] > tail[end]){
                end++;
                tail[end] = nums[i];
            }
            else{
                int left = 0;
                int right = end;
                while(left < right){
                    int mid = left + ((right - left) >>> 1);
                    if(nums[i] > tail[mid])
                        left = mid + 1;
                    else
                        right = mid;
                }
                tail[left] = nums[i];
            }
        }
        return ++end;
    }
}

这个解法的思路是创建一个一个tail数组,这个数组每个元素的含义为:
例如tail[3] = 7,表示长度为4的上升子序列中最后一个元素为7,这个解法的妙处在于可以使用贪心的思想来保证tail数组一定是有序的,有序之后就可以使用二分查找来简化时间复杂度,那么为什么tail数组一定是有序的呢,这里参考官方题解的一个整明:
image.png
讲每个最长的子序列的最后一个数字一个更新为最少,这样出现下一个元素时就更加有可能被这个序列接受,贪婪,太贪婪了,这样在遍历nums数组的过程中,如果比tail[end]大的话直接插入,否则在有序的tail数组中进行二分查找,找到这个元素要对哪一个数字进行更新,也就是找到所有大于这个数的数字中最小的一个

说一自己经常犯的一个错误,就是位运算的优先级问题:
int mid = left + (right - left) >>> 2;
这个取得数组中间索引的方法乍一看没有什么问题,但是我总是忽略运算的优先级,应该是这样婶的:
int mid = left + ((right - left) >>> 2);
加括号,加括号,在IDEA上面debug才找出这个错误