Easy

题目描述

给定一个未经排序的整数数组 nums，返回最长连续递增子序列的长度（即子数组）。序列必须严格递增。

连续递增子序列由两个索引 l 和 r（l < r）定义，表示为 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]，并且对于每个 l <= i < r，都有 nums[i] < nums[i + 1]。

示例 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

解题思路

解题思路

这道题要求找到数组中最长连续递增子序列的长度，关键在于理解"连续"的含义，即子序列的元素在原数组中必须相邻。

方法一：滑动窗口/双指针 使用双指针 left 和 right 来维护当前递增序列的窗口。当发现 nums[right] <= nums[right-1] 时，说明递增序列中断，需要更新 left 指针到当前位置，重新开始计算。

方法二：单指针扫描 使用一个变量 currentLength 记录当前递增序列长度，遍历数组时：

  • 如果当前元素大于前一个元素，递增序列长度加1
  • 否则重置长度为1，开始新的递增序列

两种方法时间复杂度相同，推荐使用方法二，代码更简洁直观。

无论哪种方法，都需要在遍历过程中实时更新最大长度，确保不漏掉任何可能的最长序列。

代码实现

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int maxLength = 1;
        int currentLength = 1;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                currentLength++;
            } else {
                currentLength = 1;
            }
            maxLength = max(maxLength, currentLength);
        }
        
        return maxLength;
    }
};

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        max_length = 1
        current_length = 1
        
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                current_length += 1
            else:
                current_length = 1
            max_length = max(max_length, current_length)
        
        return max_length

public class Solution {
    public int FindLengthOfLCIS(int[] nums) {
        int maxLength = 1;
        int currentLength = 1;
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] > nums[i - 1]) {
                currentLength++;
            } else {
                currentLength = 1;
            }
            maxLength = Math.Max(maxLength, currentLength);
        }
        
        return maxLength;
    }
}

var findLengthOfLCIS = function(nums) {
    let maxLength = 1;
    let currentLength = 1;
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            currentLength++;
        } else {
            currentLength = 1;
        }
        maxLength = Math.max(maxLength, currentLength);
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度说明
单指针扫描O(n)O(1)一次遍历，常数空间
双指针O(n)O(1)同样一次遍历，常数空间

相关题目