LeetCode 674. 最长连续递增序列

约 4 分钟
文章信息 11 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 腾讯 字节 美团 拼多多 网易 猿辅导
标签
数组

题目描述

✅ 674. 最长连续递增序列

image-20260928222313798

题意分析

返回原数组中最长连续严格递增区间的长度。连续意味着不能跳过中间元素，严格递增意味着相邻元素必须满足后一个大于前一个，相等也会使递增中断。

解法：一次扫描维护当前长度

核心思路

[!blue]

令 cur 表示以当前元素结尾的最长连续递增区间长度。处理 nums[i] 时，只需要看它与 nums[i-1] 的关系：

  • 若 nums[i] > nums[i-1]，前一个位置结尾的整个递增区间都能接上当前元素，令 cur 加一。任何以当前位置结尾、长度大于一的合法区间都必须经过前一个元素，所以直接延长前一段就是最优选择。
  • 否则，任何跨过这两个相邻元素的区间都不满足严格递增。连续性又不允许跳过前一个元素，因此只能从当前元素重新开始，令 cur = 1。

再用 ans 保存所有已处理位置中最大的 cur。每个连续区间都有一个终点，扫描完所有终点，也就找到了全局最长的区间。

解题步骤

  1. 空数组返回 0。非空时，第一个元素自身构成长度为 1 的递增区间，初始化 cur = ans = 1。
  2. 从下标 1 开始，与前一个元素比较：严格变大则 cur++，否则重置为 1。
  3. 每次更新 cur 后，立即用它更新 ans，保留中途已经出现的最长区间。
  4. 扫描结束后返回 ans。只有一个元素时不进入循环，结果自然为 1。

代码实现

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int cur = 1;
        int ans = 1;

        for (int i = 1; i < nums.length; i++) {
            // 不再严格递增时，从当前元素重新开始，长度仍为一。
            cur = nums[i] > nums[i - 1] ? cur + 1 : 1;
            ans = Math.max(ans, cur);
        }

        return ans;
    }
}

func findLengthOfLCIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    cur, ans := 1, 1
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            cur++
        } else {
            // 不再严格递增时，从当前元素重新开始，长度仍为一。
            cur = 1
        }
        if cur > ans {
            ans = cur
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$，n 为数组长度，每个元素只处理一次。
  • 空间复杂度：$O(1)$，只维护当前区间长度与全局最大长度。

关键点总结

[!green]

  • 连续性保证当前区间只能由前一个位置的区间延长，或从当前元素重新开始。
  • cur 必须以当前位置结尾，ans 才记录整个数组的最优答案。
  • 递增中断时，当前元素仍能独立构成长度为 1 的区间。

易错点总结

[!yellow]

  • 使用 >= 判断递增：相邻元素相等也应断开，题目要求严格递增。
  • 中断后把 cur 设为 0：会漏算当前元素，应重置为 1。
  • 中断后继续累加旧长度：会把不连续的多个递增段拼接起来。
  • 直接返回最后的 cur：最长区间可能早已结束，应在每轮更新并最终返回 ans。
  • 先排序再统计：排序改变了原数组的相邻关系，得到的已不是题目要求的连续区间。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 两题都要求严格递增；300允许跳过元素，本题必须连续，当前值小于或等于前一值时都要把当前长度重置为1。
978. 最长湍流子数组 中等 同样统计连续趋势段，原题要求升降交替，本题只允许一直严格上升。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/21382795
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！