Easy

题目描述

给你一个下标从 0 开始的整数数组 nums 。如果下标 i 周围存在不等的邻居，且 nums[i] 大于所有邻居，则下标 i 是 nums 中的一个 山峰 。类似地，如果下标 i 周围存在不等的邻居，且 nums[i] 小于所有邻居，则下标 i 是 nums 中的一个 山谷 。相邻的下标 i 和 j ，如果 nums[i] == nums[j] ，则它们属于 同一个 山峰或山谷。

注意，要成为山峰或山谷，下标 i 必须 左右两侧都存在 不等的邻居。

返回 nums 中 山峰和山谷的数量 。

示例 1：

输入：nums = [2,4,1,1,6,5]
输出：3
解释：
下标 0：左侧不存在不等邻居，所以下标 0 既不是山峰也不是山谷。
下标 1：最近的不等邻居是 2 和 1 。由于 4 > 2 且 4 > 1 ，下标 1 是一个山峰。
下标 2：最近的不等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 2 是一个山谷。
下标 3：最近的不等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 3 是一个山谷，但需要注意它与下标 2 属于同一个山谷。
下标 4：最近的不等邻居是 1 和 5 。由于 6 > 1 且 6 > 5 ，下标 4 是一个山峰。
下标 5：右侧不存在不等邻居，所以下标 5 既不是山峰也不是山谷。
共有 3 个山峰和山谷，所以返回 3 。

示例 2：

输入：nums = [6,6,5,5,4,1]
输出：0
解释：
下标 0：左侧不存在不等邻居，所以下标 0 既不是山峰也不是山谷。
下标 1：左侧不存在不等邻居，所以下标 1 既不是山峰也不是山谷。
下标 2：最近的不等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 2 既不是山峰也不是山谷。
下标 3：最近的不等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 3 既不是山峰也不是山谷。
下标 4：最近的不等邻居是 5 和 1 。由于 4 < 5 且 4 > 1 ，下标 4 既不是山峰也不是山谷。
下标 5：右侧不存在不等邻居，所以下标 5 既不是山峰也不是山谷。
共有 0 个山峰和山谷，所以返回 0 。

提示：

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

解题思路

这道题需要找到数组中的山峰和山谷，关键在于理解题目要求：

  1. 山峰：当前值大于左右最近的不相等邻居
  2. 山谷：当前值小于左右最近的不相等邻居
  3. 重要约束：相邻的相等元素属于同一个山峰/山谷，不能重复计算

解题思路：

最直观的方法是预处理数组，去除连续相等的元素，只保留每组相等元素中的一个代表。这样可以避免重复计算问题。

具体步骤：

  1. 遍历原数组，将不连续的元素加入新数组（即去重连续相等元素）
  2. 在去重后的数组中，检查每个位置（除首尾）是否为山峰或山谷
  3. 山峰条件：arr[i] > arr[i-1] && arr[i] > arr[i+1]
  4. 山谷条件：arr[i] < arr[i-1] && arr[i] < arr[i+1]

另一种方法是直接在原数组上操作，为每个位置找到左右最近的不相等邻居，但实现相对复杂。

推荐解法：预处理去重法，代码简洁，逻辑清晰。

时间复杂度O(n)，空间复杂度O(n)，对于题目约束完全够用。

代码实现

class Solution {
public:
    int countHillValley(vector<int>& nums) {
        vector<int> arr;
        arr.push_back(nums[0]);
        
        // 去除连续相等的元素
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i-1]) {
                arr.push_back(nums[i]);
            }
        }
        
        int count = 0;
        // 检查去重后数组的每个位置（除首尾）
        for (int i = 1; i < arr.size() - 1; i++) {
            if ((arr[i] > arr[i-1] && arr[i] > arr[i+1]) || 
                (arr[i] < arr[i-1] && arr[i] < arr[i+1])) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        arr = [nums[0]]
        
        # 去除连续相等的元素
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                arr.append(nums[i])
        
        count = 0
        # 检查去重后数组的每个位置（除首尾）
        for i in range(1, len(arr) - 1):
            if (arr[i] > arr[i-1] and arr[i] > arr[i+1]) or \
               (arr[i] < arr[i-1] and arr[i] < arr[i+1]):
                count += 1
        
        return count

public class Solution {
    public int CountHillValley(int[] nums) {
        List<int> arr = new List<int>();
        arr.Add(nums[0]);
        
        // 去除连续相等的元素
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] != nums[i-1]) {
                arr.Add(nums[i]);
            }
        }
        
        int count = 0;
        // 检查去重后数组的每个位置（除首尾）
        for (int i = 1; i < arr.Count - 1; i++) {
            if ((arr[i] > arr[i-1] && arr[i] > arr[i+1]) || 
                (arr[i] < arr[i-1] && arr[i] < arr[i+1])) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countHillValley = function(nums) {
    const arr = [nums[0]];
    
    // 去除连续相等的元素
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i-1]) {
            arr.push(nums[i]);
        }
    }
    
    let count = 0;
    // 检查去重后数组的每个位置（除首尾）
    for (let i = 1; i < arr.length - 1; i++) {
        if ((arr[i] > arr[i-1] && arr[i] > arr[i+1]) || 
            (arr[i] < arr[i-1] && arr[i] < arr[i+1])) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，一次去重，一次统计
空间复杂度O(n)最坏情况下新数组大小与原数组相同

相关题目