计算给定数组局部极值的C++代码

---

极值是指最小值或最大值。换句话说，它是一个数字或元素，它大于或小于其两个相邻值。

假设我们有一个包含n个元素的数组A。该数组A[i]中的一个元素被称为局部最小值，当且仅当它严格小于其两个相邻元素。如果它严格大于其相邻元素，则它将是局部最大值。对于A[0]和A[n-1]，由于只有一个邻居，它们既不是最大值也不是最小值。我们必须找到给定数组中局部极值的个数。

对于给定的一组数字，第一个和最后一个数字永远不可能是极值。在给定的数组中，我们可以使用各种C++技术找到这样的局部极值。

输入输出场景

考虑数组中的一组N个元素。然后，我们可以计算数组中存在的局部极值的总数。

Input: numbers = 12, 16, 4
Output: 1
Input: numbers = 10, 16, 12, 5, 23, 40
Output: 2

使用for循环

在这种方法中，我们将使用一个for循环，该循环将从给定数组的第二个元素迭代到倒数第二个元素。这是因为第一个和最后一个元素永远不可能是极值。在循环中，我们将使用if语句检查每个元素是否大于或小于其两个相邻元素。如果任一条件为真，则num变量递增一。

示例

#include <iostream>
using namespace std;
int numberOfExtrema(int x[], int N){
   int num = 0;
   // Iterate the loop from the second
   // element to the second last element
   for(int i = 1; i < N-1; i++){
      if(x[i] > x[i-1] && x[i] > x[i+1]){
         num++;
      }
      if(x[i] < x[i-1] && x[i] < x[i+1]){
         num++;
      }
   }
   return num;
}
int main() {
   int x[] = {10, 16, 12, 5, 23, 40};
   int N = sizeof(x) / sizeof(x[0]);
   std::cout << "Number of local extrema in the array: " << numberOfExtrema(x, N);
   return 0;
}

输出

Number of local extrema in the array: 2

使用C++标准模板库

我们可以使用STL（标准模板库）算法的最大值和最小值运算。std::max()和std::min()是预定义函数，分别用于返回数组指定范围内的最大和最小元素。

语法

std::max_element(first, last)
std::min_element(first, last)

其中，

• first是范围开始元素的位置。

• last是范围结束元素的位置。

如果我们想找到局部极值，我们需要一次考虑三个元素（当前元素及其两个相邻元素）。因此，我们的范围包含三个元素。因此，我们在大括号内指定这三个元素。

std::max({element 1, element 2, element 3});

这里，我们从给定数组的第二个元素迭代到倒数第二个元素。我们找到x[i - 1]、x[i]、x[i + 1]中的最大和最小元素。如果当前元素等于两者中的任何一个，则num递增一。

示例

让我们来看一个例子：

#include <iostream>
#include <algorithm>
using namespace std;
int numberOfExtrema(int x[], int N){
   int num = 0;
   // Iterate the loop from the second
   // Element to the second last element
   for (int i = 1; i < N - 1; i++) {
      int max_element = std::max({x[i - 1], x[i], x[i + 1]});
      int min_element = std::min({x[i - 1], x[i], x[i + 1]});
      if (x[i] == max_element || x[i] == min_element) {
         num++;
      }
   }
   return num;
}
int main() {
   int x[] = {10, 16, 12, 5, 23, 40};
   int N = sizeof(x) / sizeof(x[0]);
   std::cout << "Number of local extrema in the array: " << numberOfExtrema(x,N);
   return 0;
}

输出

Number of local extrema in the array: 2

使用递归

在这里，我们将使用递归来解决我们的问题。我们将数组划分为更小的子数组，并在其中找到中心值。然后，我们检查中心元素是否大于或小于其两个相邻元素。

如果满足任一条件，则num变量递增一。由于递归函数自身调用，所有结果都将组合以给出最终输出。

示例

#include <iostream>
int recursion(int x[], int left, int right) {
   // If subarray contains 2 or less elements
   if (right - left <= 1) {
      return 0;
   }
   int center = left + (right - left) / 2;
   int num = 0;
   if ((x[center] > x[center - 1] && x[center] > x[center + 1]) ||
   (x[center] < x[center - 1] && x[center] < x[center + 1])) {
      num++;
   }
   num += recursion(x, left, center);
   num += recursion(x, center, right);
   return num;
}
int numberOfExtrema(int x[], int N) {
   return recursion(x, 0, N - 1);
}
int main() {
   int x[] = {10, 16, 12, 5, 23, 40};
   int N = sizeof(x) / sizeof(x[0]);
   std::cout << "Number of local extrema in the array: " << numberOfExtrema(x, N) << std::endl;
   return 0;
}

输出

Number of local extrema in the array: 2

结论

在本文中，我们讨论了在数组中查找局部极值的几种不同方法。在第一种方法中，我们学习了简单的迭代方法，其中涉及使用for循环。在第二种方法中，我们使用了std::max()和std::min()函数。在第三种方法中，我们讨论了递归方法，该方法对于较大的数组很有用。