2210. 统计数组中峰和谷的数量

🟢   🔖  数组  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums. An index i is part of a hill in nums if the closest non-equal neighbors of i are smaller than nums[i]. Similarly, an index i is part of a valley in nums if the closest non-equal neighbors of i are larger than nums[i]. Adjacent indices i and j are part of the same hill or valley if nums[i] == nums[j].

Note that for an index to be part of a hill or valley, it must have a non- equal neighbor on both the left and right of the index.

Return the number of hills and valleys in nums.

Example 1:

Input: nums = [2,4,1,1,6,5]

Output: 3

Explanation:

At index 0: There is no non-equal neighbor of 2 on the left, so index 0 is neither a hill nor a valley.

At index 1: The closest non-equal neighbors of 4 are 2 and 1. Since 4 > 2 and 4 > 1, index 1 is a hill.

At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 2 is a valley.

At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1 < 4 and 1 < 6, index 3 is a valley, but note that it is part of the same valley as index 2.

At index 4: The closest non-equal neighbors of 6 are 1 and 5. Since 6 > 1 and 6 > 5, index 4 is a hill.

At index 5: There is no non-equal neighbor of 5 on the right, so index 5 is neither a hill nor a valley.

There are 3 hills and valleys so we return 3.

Example 2:

Input: nums = [6,6,5,5,4,1]

Output: 0

Explanation:

At index 0: There is no non-equal neighbor of 6 on the left, so index 0 is neither a hill nor a valley.

At index 1: There is no non-equal neighbor of 6 on the left, so index 1 is neither a hill nor a valley.

At index 2: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 2 is neither a hill nor a valley.

At index 3: The closest non-equal neighbors of 5 are 6 and 4. Since 5 < 6 and 5 > 4, index 3 is neither a hill nor a valley.

At index 4: The closest non-equal neighbors of 4 are 5 and 1. Since 4 < 5 and 4 > 1, index 4 is neither a hill nor a valley.

At index 5: There is no non-equal neighbor of 1 on the right, so index 5 is neither a hill nor a valley.

There are 0 hills and valleys so we return 0.

Constraints:

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 100

题目大意

给你一个下标从 0 开始的整数数组 nums 。如果两侧距 i 最近的不相等邻居的值均小于 nums[i] ，则下标 i 是 nums 中，某个峰的一部分。类似地，如果两侧距 i 最近的不相等邻居的值均大于 nums[i] ，则下标 i 是 nums 中某个谷的一部分。对于相邻下标 i 和 j ，如果 nums[i] == nums[j] ， 则认为这两下标属于 同一个 峰或谷。

注意，要使某个下标所做峰或谷的一部分，那么它左右两侧必须 都 存在不相等邻居。

返回 nums 中峰和谷的数量。

示例 1：

输入： nums = [2,4,1,1,6,5]

输出： 3

解释：

在下标 0 ：由于 2 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。

在下标 1 ：4 的最近不相等邻居是 2 和 1 。由于 4 > 2 且 4 > 1 ，下标 1 是一个峰。

在下标 2 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 2 是一个谷。

在下标 3 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 3 符合谷的定义，但需要注意它和下标 2 是同一个谷的一部分。

在下标 4 ：6 的最近不相等邻居是 1 和 5 。由于 6 > 1 且 6 > 5 ，下标 4 是一个峰。

在下标 5 ：由于 5 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。

共有 3 个峰和谷，所以返回 3 。

示例 2：

输入： nums = [6,6,5,5,4,1]

输出： 0

解释：

在下标 0 ：由于 6 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。

在下标 1 ：由于 6 的左侧不存在不相等邻居，所以下标 1 既不是峰也不是谷。

在下标 2 ：5 的最近不相等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 2 既不是峰也不是谷。

在下标 3 ：5 的最近不相等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 3 既不是峰也不是谷。

在下标 4 ：4 的最近不相等邻居是 5 和 1 。由于 4 < 5 且 4 > 1 ，下标 4 既不是峰也不是谷。

在下标 5 ：由于 1 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。

共有 0 个峰和谷，所以返回 0 。

提示：

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 100

解题思路

1. 遍历数组，从第二个元素（索引 1）到倒数第二个元素（索引 n-2）。
2. 检查当前元素是否满足山峰或谷地的条件：
   • 山峰：nums[j] < nums[i] > nums[i+1]
   • 谷地：nums[j] > nums[i] < nums[i+1]
   • 如果满足，更新结果计数器 res 并移动参考点 j。
3. 跳过相邻重复值：
   • 如果 nums[i] 和前一个参考点 nums[j] 值相同，则跳过（因为重复值无法形成山峰或谷地）。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度，遍历数组一次。
• 空间复杂度：O(1)，仅使用常量级额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var countHillValley = function (nums) {
	let res = 0;
	for (let i = 1, j = 0; i < nums.length - 1; i++) {
		// 检查是否为山峰或谷地
		if (
			(nums[j] < nums[i] && nums[i] > nums[i + 1]) ||
			(nums[j] > nums[i] && nums[i] < nums[i + 1])
		) {
			res++;
			// 更新参考点
			j = i;
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
162	寻找峰值	[✓]	数组 二分查找	🟠	🀄️ 🔗
896	单调数列	[✓]	数组	🟢	🀄️ 🔗
1403	非递增顺序的最小子序列	[✓]	贪心 数组 排序	🟢	🀄️ 🔗