674. 最长连续递增序列
674. 最长连续递增序列
题目
Given an unsorted array of integers nums
, return the length of the longestcontinuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.
A continuous increasing subsequence is defined by two indices l
and r
(l < r
) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]
and for each l <= i < r
, nums[i] < nums[i + 1]
.
Example 1:
Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
Example 2:
Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.
Constraints:
1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
题目大意
给定一个未经排序的整数数组,找到最长且连续递增的子序列 ,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l
和 r
(l < r
)确定,如果对于每个 l <= i < r
,都有 nums[i] < nums[i + 1]
,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]
就是连续递增子序列。
示例 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 <= 10^4
-10^9 <= nums[i] <= 10^9
解题思路
定义变量:
count
:用于记录当前递增子序列的长度。maxLength
:记录最长递增子序列的长度。prev
:保存上一个元素的值,用于与当前元素进行比较。
遍历数组:
- 通过遍历数组
nums
,对每个元素与前一个元素进行比较。 - 如果当前元素大于前一个元素(即满足递增条件),则继续增加当前子序列的长度
count
。 - 如果当前元素不大于前一个元素(即递增序列断裂),则更新
maxLength
为count
的最大值,并重置count
为1
,表示从当前元素开始新的递增子序列。 - 更新
prev
为当前元素。
- 通过遍历数组
处理结束后的最大值:
- 遍历完成后,由于最后一个递增序列可能是最长的,因此需要在最后返回
maxLength
和count
的较大值。
- 遍历完成后,由于最后一个递增序列可能是最长的,因此需要在最后返回
复杂度分析
- 时间复杂度:
O(n)
,其中n
是数组nums
的长度,只需要遍历一次数组,因此时间复杂度是线性的。 - 空间复杂度:
O(1)
,只使用了常数空间来存储count
、maxLength
和prev
,所以空间复杂度是常数级的。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function (nums) {
let count = 0,
maxLength = 0,
prev = -Infinity; // 初始化 prev 为负无穷,确保第一个元素可以进入递增序列
for (let num of nums) {
if (num > prev) {
// 当前元素大于前一个元素,递增子序列长度加 1
count++;
} else {
// 当前元素不大于前一个元素,更新最长递增子序列长度
maxLength = Math.max(maxLength, count);
count = 1; // 重置 count 为 1,表示从当前元素开始新的递增子序列
}
prev = num; // 更新 prev 为当前元素
}
// 返回最长递增子序列的长度
return Math.max(maxLength, count);
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
673 | 最长递增子序列的个数 | 树状数组 线段树 数组 1+ | 🟠 | 🀄️ 🔗 | |
727 | 最小窗口子序列 🔒 | 字符串 动态规划 滑动窗口 | 🔴 | 🀄️ 🔗 | |
1446 | 连续字符 | [✓] | 字符串 | 🟢 | 🀄️ 🔗 |
2407 | 最长递增子序列 II | 树状数组 线段树 队列 4+ | 🔴 | 🀄️ 🔗 |