What is a hill in the "Count Hills and Valleys in an Array" problem?

A hill is an index in the array where both neighbors are smaller than the current element. The index is considered part of a hill only if the neighbors are non-equal.

How do you define a valley in this problem?

A valley is an index in the array where both neighbors are larger than the current element. Like a hill, the index must have non-equal neighbors on both sides.

What happens if the neighbors are equal in the "Count Hills and Valleys in an Array" problem?

If the neighbors are equal, the index is not considered part of a hill or valley. Only non-equal neighbors qualify for hill or valley classification.

Can the first or last elements of the array be hills or valleys?

No, because they lack both left and right neighbors. A hill or valley requires two non-equal neighbors, so these boundary elements are excluded.

How do you optimize the solution for "Count Hills and Valleys in an Array"?

By traversing the array once and checking each element's neighbors in constant time, the solution achieves O(n) time complexity. No additional space is required, making the space complexity O(1).

#2210

Easy

auto_awesome数组·driven

LeetCode 题解工作台

统计数组中峰和谷的数量

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

数组

题目描述

给你一个下标从 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

lightbulb

解题思路

方法一：遍历

我们初始化一个指针 $j$ 指向下标 $0$ 的位置，然后在 $[1, n-1]$ 的范围内遍历数组。对于每一个位置 $i$ ：

如果 $nums[i] = nums[i+1]$ ，则跳过。
否则，如果 $nums[i]$ 大于 $nums[j]$ 且 $nums[i]$ 大于 $nums[i+1]$ ，则 $i$ 是一个峰；如果 $nums[i]$ 小于 $nums[j]$ 且 $nums[i]$ 小于 $nums[i+1]$ ，则 $i$ 是一个谷。
然后，我们将 $j$ 更新为 $i$ ，继续遍历。

遍历结束后，我们就可以得到峰和谷的数量。

时间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        ans = j = 0
        for i in range(1, len(nums) - 1):
            if nums[i] == nums[i + 1]:
                continue
            if nums[i] > nums[j] and nums[i] > nums[i + 1]:
                ans += 1
            if nums[i] < nums[j] and nums[i] < nums[i + 1]:
                ans += 1
            j = i
        return ans

speed

复杂度分析

指标	值
时间	O(n^2)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's ability to efficiently check neighbor conditions without iterating unnecessarily.
question_mark
Assess how well they handle edge cases, like arrays where no hills or valleys exist.
question_mark
Evaluate their understanding of traversing arrays and managing boundaries while avoiding extra memory usage.

warning

常见陷阱

外企场景

error
Confusing equal adjacent elements as hills or valleys when they should be skipped.
error
Overcomplicating the algorithm by adding unnecessary loops or checks.
error
Forgetting to account for boundary elements (first and last elements) that lack both left and right neighbors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count only valleys (non-hill elements).
arrow_right_alt
Return the total number of hills and valleys as separate counts.
arrow_right_alt
Modify the problem to identify peaks (strictly larger than both neighbors) and valleys (strictly smaller than both neighbors).

help

常见问题

外企场景

继续练习

#2208 将数组和减半的最少操作次数 #2212 射箭比赛中的最大得分 #2213 由单个字符重复的最长子字符串