3105. 最长的严格递增或递减子数组

🟢   🔖  数组  🔗 力扣 LeetCode

题目

You are given an array of integers nums. Return _the length of thelongest subarray of _nums which is eitherstrictly increasing or strictly decreasing.

Example 1:

Input: nums = [1,4,3,3,2]

Output: 2

Explanation:

The strictly increasing subarrays of nums are [1], [2], [3], [3], [4], and [1,4].

The strictly decreasing subarrays of nums are [1], [2], [3], [3], [4], [3,2], and [4,3].

Hence, we return 2.

Example 2:

Input: nums = [3,3,3,3]

Output: 1

Explanation:

The strictly increasing subarrays of nums are [3], [3], [3], and [3].

The strictly decreasing subarrays of nums are [3], [3], [3], and [3].

Hence, we return 1.

Example 3:

Input: nums = [3,2,1]

Output: 3

Explanation:

The strictly increasing subarrays of nums are [3], [2], and [1].

The strictly decreasing subarrays of nums are [3], [2], [1], [3,2], [2,1], and [3,2,1].

Hence, we return 3.

Constraints:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

题目大意

给你一个整数数组 nums 。

返回数组 nums 中 严格递增 或 **严格递减 **的最长非空子数组的长度。

示例 1：

输入： nums = [1,4,3,3,2]

输出： 2

解释：

nums 中严格递增的子数组有[1]、[2]、[3]、[3]、[4] 以及 [1,4] 。

nums 中严格递减的子数组有[1]、[2]、[3]、[3]、[4]、[3,2] 以及 [4,3] 。

因此，返回 2 。

示例 2：

输入： nums = [3,3,3,3]

输出： 1

解释：

nums 中严格递增的子数组有 [3]、[3]、[3] 以及 [3] 。

nums 中严格递减的子数组有 [3]、[3]、[3] 以及 [3] 。

因此，返回 1 。

示例 3：

输入： nums = [3,2,1]

输出： 3

解释：

nums 中严格递增的子数组有 [3]、[2] 以及 [1] 。

nums 中严格递减的子数组有 [3]、[2]、[1]、[3,2]、[2,1] 以及 [3,2,1] 。

因此，返回 3 。

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50

解题思路

1. 变量定义

   • prev: 记录前一个元素值，用于比较。
   • increase: 当前递增子数组长度。
   • decrease: 当前递减子数组长度。
   • maxIncrease: 遍历过程中记录的最大递增长度。
   • maxDecrease: 遍历过程中记录的最大递减长度。

2. 遍历规则

   • 递增情况 (num > prev)：
     • 重置 decrease 为 1。
     • 递增长度 increase 加 1，并更新 maxIncrease。
   • 递减情况 (num < prev)：
     • 重置 increase 为 1。
     • 递减长度 decrease 加 1，并更新 maxDecrease。
   • 相等情况 (num == prev)：
     • 同时重置 increase 和 decrease 为 1。

3. 终止条件 遍历完成后，返回 maxIncrease 和 maxDecrease 中的较大值，即为最终结果。

复杂度分析

• 时间复杂度：O(n)，只需一次线性遍历。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestMonotonicSubarray = function (nums) {
	let prev = nums[0];
	let increase = 1;
	let decrease = 1;
	let maxIncrease = 1;
	let maxDecrease = 1;
	for (let i = 1; i < nums.length; i++) {
		const num = nums[i];
		if (num > prev) {
			decrease = 1;
			increase++;
			maxIncrease = Math.max(increase, maxIncrease);
		} else if (num < prev) {
			increase = 1;
			decrease++;
			maxDecrease = Math.max(decrease, maxDecrease);
		} else {
			increase = 1;
			decrease = 1;
		}
		prev = num;
	}
	return Math.max(maxIncrease, maxDecrease);
};