leetcode300.最长递增子序列_最长递增子序列leetcode

一.题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：

你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

二.题目解析

public int lengthOfLIS(int[] nums) {
        /*动态规划，状态：dp[i]表示以第i个元素为结尾的上升子序列的长度，
        时间复杂度O(n^2),空间复杂度O(n)（遍历到一个新数的时候，之前所有的状态值都得保留，因此无法优化空间）
        * */
        int[] dp = new int[nums.length];
        //base case初始化
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length; i++) {
            int iMax = dp[i];
            int cur = nums[i];
            //只有比当前元素小（可能有多个），当前位置的元素才有可能作为结尾
            for (int j = i - 1; j >= 0; j--) {
                if(cur > nums[j]){
                    //状态转移方程
                    iMax = Math.max(iMax,dp[j] + 1);
                }
            }
            dp[i] = iMax;
        }
        int res = dp[0];
        //还需一趟遍历寻找全局最长上升子序列
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res,dp[i]);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public int lengthOfLIS(int[] nums){
        /*贪心算法+二分法，在为minnums数组新增元素的过程中，
        为了尽可能贪心的增加递增子序列的长度，用潜力大（值小）的元素替换掉潜力小（值大）的元素，
        潜力大的才有可能构成更长的序列
        时间复杂度O(nlogn),空间复杂度O(n)
        * */
        //我们维护的数组表示长度为 i+1 的最长递增子序列的最小末尾数字(数组索引0对应上升子序列长度为1)
        int[] minnums = new int[nums.length];
        minnums[0] = nums[0];
        //max记录遍历过程中的"当前的"最长上升子序列长度
        int max = 1;
     
        for (int i = 1; i < nums.length; i++) {
            //获取之前上升子序列的最后一个元素
            int rightVal = minnums[max - 1];
            //如果当前处理元素比最后一个元素大那么就“扩展”原序列，增加1个长度
            if(nums[i] > rightVal){
                minnums[max] = nums[i];
                max++;
                //如果当前处理元素比最后一个元素小那么就二分法搜索这个更具潜力的元素合适的插入位置
            }else if(nums[i] < rightVal){
                int left = 0,right = max - 1;
                while (left < right){
                    int middle = left + ((right - left) >> 1);
                    if(nums[i] <= minnums[middle]){
                        //缩短区间：left-middle
                        right = middle;
                    }else if(nums[i] > minnums[middle]){
                        //缩短区间：middle+1-right
                        left = middle + 1;
                    }else{
                        break;
                    }
                }
                
                minnums[left] = nums[i];
              
            }
            //如果当前处理元素和最后一个元素相等那么不予处理，继续向后遍历
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

优化：如果当前遍历的元素和已知的最长上升子序列某个元素相等，那这个二分搜索位置的过程就可以提前终止

public int lengthOfLIS1(int[] nums){
        /*贪心算法+二分法，在为minnums数组新增元素的过程中，
        为了尽可能贪心的增加递增子序列的长度，用潜力大（值小）的元素替换掉潜力小（值大）的元素，
        潜力大的才有可能构成更长的序列
        时间复杂度O(nlogn),空间复杂度O(n)
        * */
        //我们维护的数组表示长度为 i+1 的最长递增子序列的最小末尾数字(数组索引0对应上升子序列长度为1)
        int[] minnums = new int[nums.length];
        minnums[0] = nums[0];
        //max记录遍历过程中的"当前的"最长上升子序列长度
        int max = 1;
        //******优化：如果当前遍历的元素和已知的最长上升子序列某个元素相等，那这个二分搜索位置的过程就可以提前终止*********
        int skip = 0;
        for (int i = 1; i < nums.length; i++) {
            //获取之前上升子序列的最后一个元素
            int rightVal = minnums[max - 1];
            //如果当前处理元素比最后一个元素大那么就“扩展”原序列，增加1个长度
            if(nums[i] > rightVal){
                minnums[max] = nums[i];
                max++;
                //如果当前处理元素比最后一个元素小那么就二分法搜索这个更具潜力的元素合适的插入位置
            }else if(nums[i] < rightVal){
                int left = 0,right = max - 1;
                while (left < right){
                    int middle = left + ((right - left) >> 1);
                    if(nums[i] < minnums[middle]){
                        //缩短区间：left-middle
                        right = middle;
                    }else if(nums[i] > minnums[middle]){
                        //缩短区间：middle+1-right
                        left = middle + 1;
                    }else{
                        //当前处理元素如果等于当前最长子序列中的某个元素那么可以直接跳过当前元素
                        skip = 1;
                        break;
                    }
                }
                //如果提前终止了skip==1那么就无需赋值，否则会发生错误
                if(skip == 0) {
                    minnums[left] = nums[i];
                }
            }
            //如果当前处理元素和最后一个元素相等那么不予处理，继续向后遍历
            //初始化skip为不跳过
            skip = 0;
        }
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

参考文章：
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/yi-bu-yi-bu-tui-dao-chu-guan-fang-zui-you-jie-fa-x/