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.
Input: nums =[2,4,1,1,6,5]Output: 3Explanation:
At index 0: There is no non-equal neighbor of 2 on the left, so index 0is 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 1is a hill.At index 2: The closest non-equal neighbors of 1 are 4 and 6. Since 1<4 and 1<6, index 2is a valley.At index 3: The closest non-equal neighbors of 1 are 4 and 6. Since 1<4 and 1<6, index 3is 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 4is a hill.At index 5: There is no non-equal neighbor of 5 on the right, so index 5is neither a hill nor a valley.There are 3 hills and valleys so we return3.
Input: nums =[6,6,5,5,4,1]Output: 0Explanation:
At index 0: There is no non-equal neighbor of 6 on the left, so index 0is neither a hill nor a valley.At index 1: There is no non-equal neighbor of 6 on the left, so index 1is 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 2is 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 3is 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 4is neither a hill nor a valley.At index 5: There is no non-equal neighbor of 1 on the right, so index 5is neither a hill nor a valley.There are 0 hills and valleys so we return0.
To accurately count hills and valleys, we need to compare each element to its closest non-equal neighbors on both sides. We skip consecutive duplicates to avoid counting the same hill or valley multiple times. The key is to ensure both left and right non-equal neighbors exist before making the comparison.
classSolution {
public:int countHillValley(vector<int>& nums) {
int ans =0, n = nums.size();
for(int i =1; i < n; i++){
if(nums[i] == nums[i-1]) continue; // same hill or valley
int left = i -1, right = i +1;
while(left >=0&& nums[left] == nums[i]) left--;
if(left <0) continue; // no left neighbour found
while(right < n && nums[right] == nums[i]) right++;
if(right == n) continue; // no right neighbour found
if(nums[left] < nums[i] && nums[right] < nums[i]) ans++;
elseif(nums[left] > nums[i] && nums[right] > nums[i]) ans++;
}
return ans;
}
};
funccountHillValley(nums []int) int {
ans, n:=0, len(nums)
fori:=1; i < n; i++ {
ifnums[i] ==nums[i-1] {
continue// same hill or valley }
left, right:=i-1, i+1forleft>=0&&nums[left] ==nums[i] {
left-- }
ifleft < 0 {
continue// no left neighbour found }
forright < n&&nums[right] ==nums[i] {
right++ }
ifright==n {
continue// no right neighbour found }
ifnums[left] < nums[i] &&nums[right] < nums[i] {
ans++ } elseifnums[left] > nums[i] &&nums[right] > nums[i] {
ans++ }
}
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
publicintcountHillValley(int[] nums) {
int ans = 0, n = nums.length;
for(int i = 1; i < n; i++){
if(nums[i]== nums[i-1]) continue; // same hill or valleyint left = i - 1, right = i + 1;
while(left >= 0 && nums[left]== nums[i]) left--;
if(left < 0) continue; // no left neighbour foundwhile(right < n && nums[right]== nums[i]) right++;
if(right == n) continue; // no right neighbour foundif(nums[left]< nums[i]&& nums[right]< nums[i]) ans++;
elseif(nums[left]> nums[i]&& nums[right]> nums[i]) ans++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funcountHillValley(nums: IntArray): Int {
var ans = 0val n = nums.size
for (i in1 until n) {
if (nums[i] == nums[i-1]) continue// same hill or valley
var left = i - 1var right = i + 1while (left >=0&& nums[left] == nums[i]) left--if (left < 0) continue// no left neighbour found
while (right < n && nums[right] == nums[i]) right++if (right == n) continue// no right neighbour found
if (nums[left] < nums[i] && nums[right] < nums[i]) ans++elseif (nums[left] > nums[i] && nums[right] > nums[i]) ans++ }
return ans
}
}
classSolution:
defcountHillValley(self, nums: list[int]) -> int:
ans, n =0, len(nums)
for i in range(1, n):
if nums[i] == nums[i-1]:
continue# same hill or valley left, right = i-1, i+1while left >=0and nums[left] == nums[i]:
left -=1if left <0:
continue# no left neighbour foundwhile right < n and nums[right] == nums[i]:
right +=1if right == n:
continue# no right neighbour foundif nums[left] < nums[i] and nums[right] < nums[i]:
ans +=1elif nums[left] > nums[i] and nums[right] > nums[i]:
ans +=1return ans
impl Solution {
pubfncount_hill_valley(nums: Vec<i32>) -> i32 {
let n = nums.len();
letmut ans =0;
for i in1..n {
if nums[i] == nums[i-1] {
continue; // same hill or valley
}
letmut left = i asi32-1;
letmut right = i +1;
while left >=0&& nums[left asusize] == nums[i] {
left -=1;
}
if left <0 {
continue; // no left neighbour found
}
while right < n && nums[right] == nums[i] {
right +=1;
}
if right == n {
continue; // no right neighbour found
}
if nums[left asusize] < nums[i] && nums[right] < nums[i] {
ans +=1;
} elseif nums[left asusize] > nums[i] && nums[right] > nums[i] {
ans +=1;
}
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
countHillValley(nums: number[]):number {
letans=0, n=nums.length;
for (leti=1; i<n; i++) {
if (nums[i] ===nums[i-1]) continue; // same hill or valley
letleft=i-1, right=i+1;
while (left>=0&&nums[left] ===nums[i]) left--;
if (left<0) continue; // no left neighbour found
while (right<n&&nums[right] ===nums[i]) right++;
if (right===n) continue; // no right neighbour found
if (nums[left] <nums[i] &&nums[right] <nums[i]) ans++;
elseif (nums[left] >nums[i] &&nums[right] >nums[i]) ans++;
}
returnans;
}
}