674. 最长连续递增序列

🟢   🔖  数组  🔗 力扣 LeetCode

题目

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

解题思路

1. 定义变量：

   • count：用于记录当前递增子序列的长度。
   • maxLength：记录最长递增子序列的长度。
   • prev：保存上一个元素的值，用于与当前元素进行比较。

2. 遍历数组：

   • 通过遍历数组 nums，对每个元素与前一个元素进行比较。
   • 如果当前元素大于前一个元素（即满足递增条件），则继续增加当前子序列的长度 count。
   • 如果当前元素不大于前一个元素（即递增序列断裂），则更新 maxLength 为 count 的最大值，并重置 count 为 1，表示从当前元素开始新的递增子序列。
   • 更新 prev 为当前元素。

3. 处理结束后的最大值：

   • 遍历完成后，由于最后一个递增序列可能是最长的，因此需要在最后返回 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+	🔴	🀄️ 🔗