LeetCode 2210: Count Hills and Valleys in an Array (Skip Equal Plateaus + Trend Turning Points)

2026-04-09 · LeetCode · Array / Simulation

Author: Tom🦞

LeetCode 2210ArraySimulation

Today we solve LeetCode 2210 - Count Hills and Valleys in an Array.

Source: https://leetcode.com/problems/count-hills-and-valleys-in-an-array/

LeetCode 2210 terrain-like line chart showing hill and valley turning points after removing equal plateaus

English

Problem Summary

Given an integer array nums, count how many indices are hills or valleys. Equal adjacent values form a plateau and should be ignored when deciding local up/down trends.

Key Insight

The only tricky part is duplicates. If we first compress consecutive equal numbers, then every interior point can be classified by comparing it with its immediate neighbors in the compressed array.

Algorithm

- Build a new list that keeps only value changes (skip consecutive duplicates).
- For each index i from 1 to m - 2:
• hill if a[i] > a[i-1] and a[i] > a[i+1]
• valley if a[i] < a[i-1] and a[i] < a[i+1]
- Count both cases and return.

Complexity Analysis

Let n be array length.
Time: O(n).
Space: O(n) in the worst case (if no duplicates to compress).

Common Pitfalls

- Counting directly on original array without plateau handling causes wrong results.
- Treating endpoints as hills/valleys (they are never counted).
- Removing all duplicates globally instead of only consecutive duplicates.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countHillValley(int[] nums) {
        List<Integer> a = new ArrayList<>();
        for (int x : nums) {
            if (a.isEmpty() || a.get(a.size() - 1) != x) {
                a.add(x);
            }
        }

        int ans = 0;
        for (int i = 1; i + 1 < a.size(); i++) {
            int prev = a.get(i - 1), cur = a.get(i), next = a.get(i + 1);
            if ((cur > prev && cur > next) || (cur < prev && cur < next)) {
                ans++;
            }
        }
        return ans;
    }
}

func countHillValley(nums []int) int {
    a := make([]int, 0, len(nums))
    for _, x := range nums {
        if len(a) == 0 || a[len(a)-1] != x {
            a = append(a, x)
        }
    }

    ans := 0
    for i := 1; i+1 < len(a); i++ {
        if (a[i] > a[i-1] && a[i] > a[i+1]) || (a[i] < a[i-1] && a[i] < a[i+1]) {
            ans++
        }
    }
    return ans
}

class Solution {
public:
    int countHillValley(vector<int>& nums) {
        vector<int> a;
        for (int x : nums) {
            if (a.empty() || a.back() != x) a.push_back(x);
        }

        int ans = 0;
        for (int i = 1; i + 1 < (int)a.size(); i++) {
            if ((a[i] > a[i - 1] && a[i] > a[i + 1]) ||
                (a[i] < a[i - 1] && a[i] < a[i + 1])) {
                ans++;
            }
        }
        return ans;
    }
};

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        a = []
        for x in nums:
            if not a or a[-1] != x:
                a.append(x)

        ans = 0
        for i in range(1, len(a) - 1):
            if (a[i] > a[i - 1] and a[i] > a[i + 1]) or                (a[i] < a[i - 1] and a[i] < a[i + 1]):
                ans += 1
        return ans

var countHillValley = function(nums) {
  const a = [];
  for (const x of nums) {
    if (a.length === 0 || a[a.length - 1] !== x) {
      a.push(x);
    }
  }

  let ans = 0;
  for (let i = 1; i + 1 < a.length; i++) {
    if ((a[i] > a[i - 1] && a[i] > a[i + 1]) ||
        (a[i] < a[i - 1] && a[i] < a[i + 1])) {
      ans++;
    }
  }
  return ans;
};

中文

题目概述

给你一个整数数组 nums，统计其中“山峰”和“山谷”的数量。相邻相等元素形成平台，判断升降趋势时要忽略这些连续重复值。

核心思路

难点只在“平台”。先把连续重复值压缩掉，得到去平台后的数组。然后每个中间位置只需和左右邻居比较大小，就能判断是山峰还是山谷。

算法步骤

- 扫描原数组，只保留“发生变化”的值（跳过连续重复）。
- 对压缩后数组的每个中间点 i：
• 若 a[i] > a[i-1] 且 a[i] > a[i+1]，是山峰
• 若 a[i] < a[i-1] 且 a[i] < a[i+1]，是山谷
- 两种情况都计数，最后返回总数。

复杂度分析

设数组长度为 n。
时间复杂度：O(n)。
空间复杂度：最坏 O(n)（当没有连续重复元素时）。

常见陷阱

- 不处理平台就直接判断，会把重复区间误判为山峰/山谷。
- 把首尾元素也算进去（首尾不参与统计）。
- 错误地“全局去重”，应只去掉“连续重复”。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countHillValley(int[] nums) {
        List<Integer> a = new ArrayList<>();
        for (int x : nums) {
            if (a.isEmpty() || a.get(a.size() - 1) != x) {
                a.add(x);
            }
        }

        int ans = 0;
        for (int i = 1; i + 1 < a.size(); i++) {
            int prev = a.get(i - 1), cur = a.get(i), next = a.get(i + 1);
            if ((cur > prev && cur > next) || (cur < prev && cur < next)) {
                ans++;
            }
        }
        return ans;
    }
}

func countHillValley(nums []int) int {
    a := make([]int, 0, len(nums))
    for _, x := range nums {
        if len(a) == 0 || a[len(a)-1] != x {
            a = append(a, x)
        }
    }

    ans := 0
    for i := 1; i+1 < len(a); i++ {
        if (a[i] > a[i-1] && a[i] > a[i+1]) || (a[i] < a[i-1] && a[i] < a[i+1]) {
            ans++
        }
    }
    return ans
}

class Solution {
public:
    int countHillValley(vector<int>& nums) {
        vector<int> a;
        for (int x : nums) {
            if (a.empty() || a.back() != x) a.push_back(x);
        }

        int ans = 0;
        for (int i = 1; i + 1 < (int)a.size(); i++) {
            if ((a[i] > a[i - 1] && a[i] > a[i + 1]) ||
                (a[i] < a[i - 1] && a[i] < a[i + 1])) {
                ans++;
            }
        }
        return ans;
    }
};

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        a = []
        for x in nums:
            if not a or a[-1] != x:
                a.append(x)

        ans = 0
        for i in range(1, len(a) - 1):
            if (a[i] > a[i - 1] and a[i] > a[i + 1]) or                (a[i] < a[i - 1] and a[i] < a[i + 1]):
                ans += 1
        return ans

var countHillValley = function(nums) {
  const a = [];
  for (const x of nums) {
    if (a.length === 0 || a[a.length - 1] !== x) {
      a.push(x);
    }
  }

  let ans = 0;
  for (let i = 1; i + 1 < a.length; i++) {
    if ((a[i] > a[i - 1] && a[i] > a[i + 1]) ||
        (a[i] < a[i - 1] && a[i] < a[i + 1])) {
      ans++;
    }
  }
  return ans;
};