LeetCode 674. 最长连续递增序列

Categories:

题目描述
思路分析
1. 解法一：贪心/线性扫描（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 674. 最长连续递增序列

思路分析

解法一：贪心/线性扫描（推荐）

核心思路：

连续递增子序列要求相邻元素严格递增，因此只需线性扫描一遍即可。

维护一个当前连续递增长度 cur，若 nums[i] > nums[i-1]，则 cur++；否则重置 cur = 1。

每次更新全局最大值 max，遍历结束后返回 max。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，仅需一次线性遍历。

空间复杂度：O(1)，只使用了常数个辅助变量。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int max = 1;
        // cur 记录以当前元素结尾的连续递增子序列长度
        int cur = 1;

        for (int i = 1; i < nums.length; i++) {
            // 当前元素大于前一个元素，连续递增长度加一
            if (nums[i] > nums[i - 1]) {
                cur++;
            } else {
                // 递增中断，重置当前长度为 1
                cur = 1;
            }
            // 更新全局最大值
            if (cur > max) {
                max = cur;
            }
        }

        return max;
    }
}

func findLengthOfLCIS(nums []int) int {
    max := 1
    // cur 记录以当前元素结尾的连续递增子序列长度
    cur := 1

    for i := 1; i < len(nums); i++ {
        // 当前元素大于前一个元素，连续递增长度加一
        if nums[i] > nums[i-1] {
            cur++
        } else {
            // 递增中断，重置当前长度为 1
            cur = 1
        }
        // 更新全局最大值
        if cur > max {
            max = cur
        }
    }

    return max
}

解法二：动态规划

核心思路：

定义 dp[i] 为以 nums[i] 结尾的最长连续递增子序列的长度。

状态转移：若 nums[i] > nums[i-1]，则 dp[i] = dp[i-1] + 1；否则 dp[i] = 1。

遍历 dp 数组取最大值即为答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，仅需一次线性遍历。

空间复杂度：O(n)，其中 n 表示 dp 数组的长度。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n = nums.length;
        // dp[i] 表示以 nums[i] 结尾的最长连续递增子序列长度
        int[] dp = new int[n];
        // 每个元素自身构成长度为 1 的子序列
        Arrays.fill(dp, 1);

        int max = 1;
        for (int i = 1; i < n; i++) {
            // 当前元素大于前一个元素，状态转移
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            // 更新全局最大值
            if (dp[i] > max) {
                max = dp[i];
            }
        }

        return max;
    }
}

func findLengthOfLCIS(nums []int) int {
    n := len(nums)
    // dp[i] 表示以 nums[i] 结尾的最长连续递增子序列长度
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }

    max := 1
    for i := 1; i < n; i++ {
        // 当前元素大于前一个元素，状态转移
        if nums[i] > nums[i-1] {
            dp[i] = dp[i-1] + 1
        }
        // 更新全局最大值
        if dp[i] > max {
            max = dp[i]
        }
    }

    return max
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	动态规划、二分查找
128. 最长连续序列	中等	哈希表
718. 最长重复子数组	中等	动态规划
53. 最大子数组和	中等	动态规划、贪心
152. 乘积最大子数组	中等	动态规划
485. 最大连续 1 的个数	简单	数组、贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/21382795