跳至主要內容

674. 最长连续递增序列


674. 最长连续递增序列

🟢   🔖  数组  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给定一个未经排序的整数数组,找到最长且连续递增的子序列 ,并返回该序列的长度。

连续递增的子序列 可以由两个下标 lrl < 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
    • 如果当前元素不大于前一个元素(即递增序列断裂),则更新 maxLengthcount 的最大值,并重置 count1,表示从当前元素开始新的递增子序列。
    • 更新 prev 为当前元素。
  3. 处理结束后的最大值

    • 遍历完成后,由于最后一个递增序列可能是最长的,因此需要在最后返回 maxLengthcount 的较大值。

复杂度分析

  • 时间复杂度O(n),其中 n 是数组 nums 的长度,只需要遍历一次数组,因此时间复杂度是线性的。
  • 空间复杂度O(1),只使用了常数空间来存储 countmaxLengthprev,所以空间复杂度是常数级的。

代码

/**
 * @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+🟠🀄️open in new window 🔗open in new window
727最小窗口子序列 🔒字符串 动态规划 滑动窗口🔴🀄️open in new window 🔗open in new window
1446连续字符[✓]字符串🟢🀄️open in new window 🔗open in new window
2407最长递增子序列 II树状数组 线段树 队列 4+🔴🀄️open in new window 🔗open in new window