统计数组中峰和谷的数量

难度: Easy

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

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        ans = 0
        i, n = 0, len(nums)
        while i < n:
            start, v = i, nums[i]
            while i < n and nums[i] == v:
                i += 1
            if start > 0 and i < n and ((nums[start - 1] < v) == (nums[i] < v)):
                ans += 1
        return ans

Explain

该题解利用两个指针，i 和 start，遍历数组 nums。对于每个元素，首先通过内部 while 循环跳过相邻的相同元素，从而定位到每个独特元素的开始和结束位置（start 和 i）。如果这个独特元素的最左侧和最右侧的不相等邻居满足峰或谷的条件（即都比它小或都比它大），则将其计为一个峰或谷。该算法只遍历数组一次，并且正确处理了相邻元素相等的情况。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        ans = 0  # 初始化峰和谷的计数
        i, n = 0, len(nums)  # i 是当前遍历的位置，n 是数组长度
        while i < n:
            start, v = i, nums[i]  # 记录当前连续相同元素的起始位置和值
            while i < n and nums[i] == v:  # 跳过所有相同的元素
                i += 1
            # 如果不是数组的边界，并且两侧元素都小于或都大于 v，则为一个峰或谷
            if start > 0 and i < n and ((nums[start - 1] < v) == (nums[i] < v)):
                ans += 1  # 增加峰或谷的计数
        return ans  # 返回峰和谷的总数

Explore

函数中通过两个主要的检查来避免越界错误。首先，内部 `while` 循环 (`while i < n and nums[i] == v`) 确保只要 `i` 指向的位置在数组范围内，就继续遍历。其次，最关键的是，在判断是否为峰或谷时，代码中有明确的边界检查 (`if start > 0 and i < n`)，这确保在比较 `nums[start - 1]` 和 `nums[i]` 时，索引 `start - 1` 和 `i` 都是有效的，从而避免越界。

代码通过跳过所有连续相同的元素解决了相同元素的影响。当找到一组连续相同的元素后，通过 `while` 循环将 `i` 增加到这些元素的末尾，然后检查这组元素的前一个和后一个不相同的元素。使用条件 `((nums[start - 1] < v) == (nums[i] < v))` 来判断这两个元素是否都大于或都小于中间元素的值 `v`。这样的比较直接排除了相同元素对判断的干扰，只关注两侧不同的元素与中间值的比较。

当 `while` 循环结束后，`i` 可能会等于数组长度 `n`，这表示已经遍历到数组的末尾。在这种情况下，如果连续相同的元素组成的序列位于数组的最末尾，它们就不会被计为峰或谷，因为它们没有右侧的邻居元素进行比较。这种设计确保只有当连续相同的元素组既有有效的左侧也有有效的右侧邻居时，才会被考虑为峰或谷。

变量 `v` 在代码中用于记录当前正在处理的一组连续相同元素的值。这对于确定峰或谷至关重要，因为峰或谷的判断依赖于这组元素的值与其左右邻居的值的比较。通过记录 `v`，我们可以轻松地将这组元素的值与其左侧（`nums[start - 1]`）和右侧（`nums[i]`）的元素进行比较，以确定是否满足峰或谷的条件。