C++程序计算本地极值个数

给定n个元素的数组。本地极值是指要么大于其两个邻居，要么小于其两个邻居的元素。您必须计算给定数组中的本地极值数量。

注意： 第一个和最后一个元素不是本地极值。

例子：

输入：a[] = {1, 5, 2, 5}
输出：2

输入：a[] = {1, 2, 3}
输出：0

方法: 计算极值的数量，我们必须检查一个元素是maxima或minima，即它是否比其邻居更大或者比邻居更小。为此，简单地遍历数组，并对每个元素检查其作为极值的可能性。

注意: a[0] 和 a[n-1] 每个只有一个邻居，他们既不是最小值也不是最大值。

// CPP to find number
// of extrema
#include <bits/stdc++.h>
using namespace std;
 
// function to find
// local extremum
int extrema(int a[], int n)
{
    int count = 0;
 
    // start loop from position 1
    // till n-1
    for (int i = 1; i < n - 1; i++)
    {
 
        // only one condition
        // will be true at a 
        // time either a[i]
        // will be greater than
        // neighbours or less
        // than neighbours
 
        // check if a[i] is greater
        // than both its neighbours
        // then add 1 to x
        count += (a[i] > a[i - 1] && a[i] > a[i + 1]);
 
        // check if a[i] is
        // less than both its
        // neighbours, then
        // add 1 to x
        count += (a[i] < a[i - 1] && a[i] < a[i + 1]);
    }
 
    return count;
}
 
// driver program
int main()
{
    int a[] = { 1, 0, 2, 1 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << extrema(a, n);
    return 0;
}

输出:

时间复杂度: 输入数组的大小为n，则为O(n)。这是因为for循环从1到n执行。