最长连续递增序列问题

题目描述

给定一个未经排序的整数数组 nums，要求找到最长连续递增子序列的长度。这里的“连续递增子序列”是指子序列中的元素在原始数组中连续排列，并且严格递增（后一个元素 > 前一个元素）。

例如：
输入：nums = [1, 3, 5, 4, 7]
输出：3
解释：最长连续递增子序列为 [1, 3, 5]，长度为 3。

解题过程循序渐进讲解

步骤1：理解问题与边界情况

• 数组可能为空，此时长度为 0。
• 数组可能只有一个元素，此时长度为 1。
• 连续递增要求元素在原数组中连续（相邻），而不是任意位置的递增子序列（后者是“最长递增子序列 LIS”，需要用动态规划或二分查找）。

步骤2：基础思路——一次遍历（贪心）

由于要求连续递增，我们只需要遍历数组一次，动态维护当前连续递增子序列的长度。

过程：

1. 初始化 max_len = 1（如果数组非空，至少长度为 1），cur_len = 1（当前连续递增子序列长度）。
2. 从下标 i = 1 开始遍历到数组末尾：
   • 如果 nums[i] > nums[i-1]，说明仍保持递增，cur_len++，并更新 max_len = max(max_len, cur_len)。
   • 否则（nums[i] <= nums[i-1]），递增中断，重置 cur_len = 1。
3. 遍历结束后，返回 max_len。

示例跟踪：
nums = [1, 3, 5, 4, 7]

• i=1：1<3 → cur_len=2, max_len=2
• i=2：3<5 → cur_len=3, max_len=3
• i=3：5>4 → 中断，cur_len=1
• i=4：4<7 → cur_len=2, max_len=3
  结果：3

步骤3：代码实现（Python）

def findLengthOfLCIS(nums):
    if not nums:
        return 0
    max_len = 1
    cur_len = 1
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            cur_len += 1
            max_len = max(max_len, cur_len)
        else:
            cur_len = 1
    return max_len

步骤4：时间复杂度与空间复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。
• 空间复杂度：O(1)，只用了常数个额外变量。

步骤5：边界情况验证

1. nums = [] → 返回 0。
2. nums = [5] → 返回 1。
3. nums = [2, 2, 2, 2] → 每次 nums[i] == nums[i-1] 都会重置 cur_len=1，所以返回 1。
4. nums = [1, 2, 3, 4, 5] → 全程递增，返回 5。

步骤6：变式问题拓展

如果题目改为最长连续非递减子序列（允许相等），则只需将判断条件 nums[i] > nums[i-1] 改为 nums[i] >= nums[i-1]。

总结

这道题的关键在于区分“连续递增子序列”与一般“最长递增子序列”，利用连续性质只需一次遍历，属于贪心思想。核心是维护当前连续递增的长度，遇到中断则重置，并始终更新全局最大值。