【LeetCode】674. 最长连续递增序列_leetcode 674.最长连续递增序列

1. 问题

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

提示：

• 1 <= nums.length <= 104
• -109 <= nums[i] <= 109

2. 解题思路

本题与300. 最长递增子序列区别在于多了两字 连续，比较的是挨着的两个数值。

2.1 双指针（滑动窗口）

• 令指针i指向连续递增序列的开始，指针j指向最后一个连续递增序列的末尾
• 当nums[j+1]>nums[j]时，j++
• 否则，计算当前连续递增序列的长度，并与当前的最大连续递增序列长度比较；大，则替换最大值；i指向 j+1，j++.

详见代码中方法 findLengthOfLCIS3。

2.2 单指针

一个指针遍历数组，初始状态，当前最大长度count=1，最终结果ans=1:

• 从 0 位置开始遍历，遍历时根据前后元素状态判断是否递增，递增则 count++，递减则 count=1
• 如果 count>ans，则更新 ans，直到循环结束
  详见代码中，方法：findLengthOfLCIS2。

2.3 动态规划

• 令dp_i 为包含nums[i]的最长连续递增子序列
• 确定递推公式： dp_i = Math.max(dp_i-1 + 1, dp_i);
• dp数组如何初始化： Arrays.fill(dp, 1);
• 确定遍历顺序：从前往后

详见代码中方法findLengthOfLCIS。进一步优化见方法 findLengthOfLCIS0。

3. 代码

class Solution {
    //双指针：i为递增序列开始，j为最后一个连续递增序列结尾索引，当前最长连续递增序列长度为 j-i
    public int findLengthOfLCIS3(int[] nums) {
        int i=0;
        int j=0;
        //因为nums至少有一个元素，则连续递增的最小值为1
        int maxLen=1;
        int len=nums.length;
        while(j<len-1){
            if(nums[j]<nums[j+1]){
                j++;
            }
            //否则，计算当前序列长度
            else {
                maxLen=Math.max(maxLen, j-i+1);
                //从不连续处开始，重新遍历
                i=j+1;
                j++;
            }
        }
        //可能正在递增，遍历结束了
        maxLen=Math.max(maxLen, j-i+1);
        return maxLen;
    }

    /**
    改进为单指针： 
    count 为当前元素峰值，ans为最大峰值
    初始化 count = 1
    从 0 位置开始遍历，遍历时根据前后元素状态判断是否递增，递增则 count++，递减则 count=1
    如果 count>ans，则更新 ans
    直到循环结束
    时间复杂度：O(N)
    */
    public int findLengthOfLCIS2(int[] nums) {
        if(nums.length <= 1)
            return nums.length;
        int ans = 1;
        int count = 1;
        for(int i=0;i<nums.length-1;i++) {
            if(nums[i+1] > nums[i]) {
                count++;
            } 
			//这里else中 不直接计算ans，是因为对于连续递增的序列 1，2，3，4，5，就不会走else；若直接写ans = count > ans ? count : ans，循环完毕，就还要计算一遍
			else {  
                count = 1;
            }
            ans = count > ans ? count : ans;
        }
        return ans;
    }

    /**
        动态规划：
        1、确定dp数组及下标含义：包含nums[i]的最长连续递增子序列
        2、确定递推公式： dp[i] = Math.max(dp[i - 1] + 1, dp[i]);
        3、dp数组如何初始化： Arrays.fill(dp, 1);
        4、确定遍历顺序：从前往后
        5、举例推导：·····

     */
     public int findLengthOfLCIS(int[] nums) {
         int maxLen=Integer.MIN_VALUE;
         int[] dp=new int[nums.length];
         //填充初始值，均为1
         Arrays.fill(dp, 1);
         //遍历
         for(int i=1; i<nums.length; i++){
             if(nums[i]>nums[i-1]){
                 dp[i]=Math.max(dp[i-1]+1, dp[i]);
             }
         }
         //找到最大值
         for(int n:dp){
             maxLen=Math.max(n, maxLen);
         }
         return maxLen;
     }

	//优化
	public int findLengthOfLCIS0(int[] nums) {
         int maxLen=1;
         int[] dp=new int[nums.length];
         //填充初始值，均为1
         Arrays.fill(dp, 1);
         //遍历
         for(int i=1; i<nums.length; i++){
             if(nums[i]>nums[i-1]){
                 dp[i]=dp[i-1]+1;
             }
             if(maxLen<dp[i]){
                 maxLen=dp[i];
             }
         }
         return maxLen;
     }
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97