当前位置:   article > 正文

【LeetCode】674. 最长连续递增序列_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 动态规划

  • 令dpi 为包含nums[i]的最长连续递增子序列
  • 确定递推公式: dpi = Math.max(dpi-1 + 1, dpi);
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/85006
推荐阅读
相关标签
  

闽ICP备14008679号