845. 数组中的最长山脉

🟠   🔖  数组 双指针 动态规划 枚举  🔗 力扣 LeetCode

题目

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.

Example 1:

Input: arr = [2,1,4,7,3,2,5]

Output: 5

Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: arr = [2,2,2]

Output: 0

Explanation: There is no mountain.

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

Follow up:

• Can you solve it using only one pass?
• Can you solve it in O(1) space?

题目大意

把符合下列属性的数组 arr 称为 山脉数组 ：

• arr.length >= 3
• 存在下标 i（0 < i < arr.length - 1），满足
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0 。

示例 1：

输入： arr = [2,1,4,7,3,2,5]

输出： 5

解释： 最长的山脉子数组是 [1,4,7,3,2]，长度为 5。

示例 2：

输入： arr = [2,2,2]

输出： 0

解释： 不存在山脉子数组。

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

进阶：

• 你可以仅用一趟扫描解决此问题吗？
• 你可以用 O(1) 空间解决此问题吗？

解题思路

要在一次遍历中找到数组中最长的山脉子数组，并且使用 O(1) 的空间，可以按照以下步骤进行：

1. 初始化：设置变量来跟踪当前山脉的长度和找到的最大山脉长度。

2. 遍历数组：使用循环遍历数组，检查每个元素是否是山脉的顶点：

   • 对于每个元素（除了第一个和最后一个），检查它是否为峰值（大于其相邻的元素）。
   • 一旦找到峰值，就向左扩展以计数上升部分的长度，再向右扩展以计数下降部分的长度。

3. 更新最大长度：找到有效的山脉后，如果当前山脉的长度大于已知的最大长度，更新最大山脉长度。

4. 跳过已处理元素：在处理完一个山脉后，更新索引 i 为右侧的最后一个元素，以跳过已经计数的部分，优化遍历。

5. 返回结果：遍历结束后，返回找到的最大山脉长度，如果没有找到山脉，则返回 0。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度，因为只遍历数组一次，并在遇到山脉时跳过已经处理的元素。
• 空间复杂度：O(1)，只使用常数级的空间来存储变量，而不随输入规模而变化。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var longestMountain = function (arr) {
	const n = arr.length;
	if (n < 3) return 0;

	let maxMountain = 0;

	for (let i = 1; i < n - 1; i++) {
		// 检查 arr[i] 是否为峰值
		if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
			let left = i - 1,
				right = i + 1;
			// 计算递增部分的长度
			while (left > 0 && arr[left] > arr[left - 1]) {
				left--;
			}
			// 计算递减部分的长度
			while (right < n - 1 && arr[right] > arr[right + 1]) {
				right++;
			}
			// 更新最长山脉子数组的长度
			maxMountain = Math.max(maxMountain, right - left + 1);
			// 跳过山脉数组中的元素
			i = right;
		}
	}
	return maxMountain;
};

相关题目

题号	标题	题解	标签	难度
1671	得到山形数组的最少删除次数	[✓]	贪心 数组 二分查找 1+
2100	适合野炊的日子		数组 动态规划 前缀和