LeetCode 674. 最长连续递增序列
目录
题目描述
题意分析
题目要的是一段「在原数组里下标连着、并且值严格变大」的区间，返回它的最长长度。这里有两个词都不能放松：连续指下标必须挨着，不允许跳过任何元素；递增指严格大于，两个相等的数不能拼进同一段。
约束信号很明确：只问长度，不问具体是哪一段，也不问有多少段。答案只依赖「相邻两个数的大小关系」这一个局部信息，因此整个数组可以只看一遍，不需要回头。
边界要先想清楚。数组为空时没有任何合法区间，返回 0；数组只有一个元素时，单个元素本身就是一段合法区间，答案是 1；数组全程不递增（例如全相等）时，每个元素各自成段，答案同样是 1。
解法：一次扫描维护当前长度
核心思路
本题要求的是连续且严格递增的子数组，因此是否能延长当前区间，只取决于相邻元素
nums[i-1]和nums[i]。扫描到下标
i时，维护不变量：cur是“以i结尾的最长连续递增子数组长度”。若nums[i] > nums[i-1]，当前元素能接到上一段末尾，cur++；否则连续递增关系已经断开，只能从nums[i]重新开始，令cur=1。ans记录所有cur的最大值。任何合法区间都有一个结束位置，扫描到该位置时，
cur会准确表示它的长度，所以取全局最大值不会漏解。与最长递增子序列不同，这里不能跳过元素，也就不需要二维 DP 或二分结构。
解题步骤
- 空数组返回 0；非空数组把
cur和ans初始化为 1。- 从下标 1 开始扫描，比较当前元素与前一个元素。
- 严格变大时令
cur++，否则令cur=1。- 每轮用
cur更新ans，最后返回ans。以
[1,3,5,4,7]为例，cur依次为1,2,3,1,2，最大值为 3，对应[1,3,5]。
代码实现
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)$，每个元素只扫描一次。
- 空间复杂度：$O(1)$，只维护当前长度和全局最大值。
关键点总结
cur表示“以当前位置结尾”的局部最优，ans才是全局最优。- 题目要求严格递增，判断条件必须是
>，相等时也要重置。- 连续性让状态只依赖前一个元素；若允许跳过元素，就变成最长递增子序列问题。
- 最长区间不一定在数组末尾，因此扫描过程中必须持续更新
ans。
易错点总结
- 把
>写成>=：[2,2,2]会被误判为长度 3，正确答案是 1。- 递增断开时不重置
cur：会把多个互不连续的递增段拼在一起。- 只在循环结束后更新答案：
[1,3,5,4]会漏掉中途结束的最优段。- 未处理空数组：把答案固定初始化为 1 会让空数组错误地返回 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 53. 最大子数组和 | 中等 | 以当前位置结尾的最优子结构 |
| 128. 最长连续序列 | 中等 | 哈希集合从段首向后扩展 |
| 300. 最长递增子序列 | 中等 | 可跳过元素的贪心加二分 |
| 485. 最大连续 1 的个数 | 简单 | 定值连续段计数 |
| 718. 最长重复子数组 | 中等 | 两数组公共连续段二维 DP |
| 1004. 最大连续1的个数 III | 中等 | 带翻转额度的滑动窗口 |
| 1493. 删掉一个元素以后全为 1 的最长子数组 | 中等 | 允许删一个元素的连续段 |