Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Problem description

You are given an array of integers with indices starting at 0, nums. If the nearest unequal neighbor to I on both sides is less than nums[I], then the subscript I is part of a peak in NUMS.

Similarly, if the nearest unequal neighbor to I on both sides has a value greater than nums[I], then the subscript I is part of a valley in NUMS. For adjacent subscripts I and j, if nums[I] == nums[j], the two subscripts are considered to belong to the same peak or valley, and the number of peaks and valleys in NUMS is returned.

Note that for a subindex to be part of a peak or valley, it must have unequal neighbors on both the left and right sides.

Number of peaks and valleys in an array.

Two, the title requirements

The sample

Input: nums = [2,4,1,1,6,5] Output: 3 Explanation: at subscript 0: since there are no unequal neighbors to the left of 2, subscript 0 is neither peak nor valley. The nearest unequal neighbors at subscript 1:4 are 2 and 1. Since 4 is greater than 2 and 4 is greater than 1, subscript 1 is a peak. The nearest unequal neighbors at subscript 2:1 are 4 and 6. Since 1 is less than 4 and 1 is less than 6, subscript 2 is a valley. The nearest unequal neighbors at subscript 3:1 are 4 and 6. Since 1 is less than 4 and 1 is less than 6, subscript 3 fits the definition of a valley but it's important to note that it's part of the same valley as subscript 2. The nearest unequal neighbors at subscript 4:6 are 1 and 5. Since 6 is greater than 1 and 6 is greater than 5, subscript 4 is a peak. At subscript 5: Since there are no unequal neighbors to the right of 5, subscript 5 is neither peak nor valley. There are three peaks and three valleys, so we return 3.Copy the code

inspection

1. Array weight judgment and loop judgment 2. It is recommended that it take 20 to 35 minutesCopy the code

Third, problem analysis

This one I just got to want to use the double pointer, but the brain is thinking about thinking about chaos, later in order to save trouble, simply direct judgment heavy output results judgment.

For example, if adjacent numbers are the same, I remove the following:

Nums = [2,4,1,1,6,5]Copy the code

So we can calculate all the elements except the beginning and the end.

So how do you get rid of adjacent numbers that are the same?

Open another array v, store the first number directly, then compare each number with the previous one, store it in the new array, otherwise continue to judge.

Four, coding implementation

class Solution {
public:
    int countHillValley(vector<int>& nums) {
        int i,j,ans=0;// Initial data
        vector<int>v;// Define an array
        v.push_back(nums[0]);// The first number
        for(i=1; i<nums.size(a); i++)// Cycle the weight
        {
            if(nums[i]! =nums[i- 1])
                v.push_back(nums[i]);
        }
        for(i=1; i<v.size(a)- 1; i++)// Peak valley calculation
        {
            if(v[i]>v[i- 1]&&v[i]>v[i+1]||v[i]<v[i- 1]&&v[i]<v[i+1])
                ans++;/ / count
        }
        return ans;// Output the result}};Copy the code

V. Test results