C++ 在最多进行一次替换的情况下，将给定数组中的峰值和低谷的数量最小化

峰值被定义为数组中的点或索引，其左右两侧的值均小于该索引处的值。低谷被定义为数组中的点或索引，其左右两侧的值均大于该索引处的值。在这个问题中，我们有一个大小为n的整数数组’array’。我们的任务是通过进行一次操作来减少给定数组中峰值和低谷的数量。操作是我们可以将给定数组的至多一个值替换为任意值。

注意：在上述问题的解释中，我们已经提到了峰值和低谷，所以要清楚的是给定数组的第0个索引和最后一个索引都不被视为峰值或低谷，因为它们没有两个邻居。

示例示例

输入

n: 5
array: [2, 1, 3, 2, 6]

输出

0

解释 ：在上面给出的大小为5的数组中，通过将第2个索引值3替换为1，峰值和谷值的计数变为0。因此，新数组变为[2, 1, 1, 2, 6]。

输入

n: 6
array: [2, 1, 3, 4, 3, 4]

输出结果

1

贪婪算法

这种方法的思想很简单，我们采用贪心策略，即我们知道第 i 个索引可以影响第 i+1 个索引或第 i-1 个索引，所以我们试图改变受到最多索引影响的第 i 个索引的值。

让我们逐步讨论这种方法：

• 我们创建了三个函数：’minCountOfPeaksTrougs’，’next’和’previous’。

• 在’minCountOfPeaksTrougs’函数中

创建一个布尔数组来标记山峰和低谷数组，同时计数

将山峰和低谷的计数存储在变量result中

再次，遍历数组，检查当前索引i是否有下一个和上一个索引。将当前数组值分别赋给下一个数组值和上一个数组值，并使用next和previous函数进行更新。

最后更新结果并返回。

• 在Next和previous函数中

两个函数都接受当前索引、数组和数组的长度作为参数，并验证当前索引是否具有山峰和低谷。

请看下面的代码以更好地理解上述方法。

例子

#include <bits/stdc++.h>
using namespace std;


// Create a function to check the next element for the current index
bool next(int i, int array[], int n){
   bool ok;
   ok = i > 0 && i < n - 1 && array[i] < array[i - 1] && array[i] < array[i + 1];
   return ok;
}
// Create a function to check the previous element for the current index
bool previous(int i, int array[], int n){
   bool ok;
   ok = i > 0 && i < n - 1 && array[i] > array[i - 1] && array[i] > array[i + 1];
   return ok;
}
// Create function minCountOfPeaksTrougs to minimize the count of Peaks and Trough  
int minCountOfPeaksTrougs(int array[], int n){
   // Create an array of boolean to store the index of peaks and troughs
   bool check[n] = { 0 };
   int cnt = 0;
   // Traverse given array to check the troughs and peaks
   for (int i = 1; i < n- 1; i++) {
      //If both the neighbors are greater than the current index is peaks
      if (array[i] > array[i - 1] && array[i] > array[i + 1]){
         check[i] = 1;
         cnt++;
      }
      //If both the neighbors are smaller than the current index is trough
      else if (array[i] < array[i - 1] && array[i] < array[i + 1]){
         check[i] = 1;
         cnt++;
      }
   }
   // Create variable result and initialized With the count of peaks and troughs
   int result = cnt;
   // Traverse the array
   for (int i = 1; i < n - 1; i++) {
      int curVal = array[i];
      // If we make the current array value as next array value
      array[i] = array[i + 1];
      int temp = cnt -check[i - 1] -check[i] -check[i + 1] +next(i - 1, array, n) +previous(i - 1, array, n) +next(i, array, n) +previous(i, array, n) +next(i + 1, array, n) +previous(i + 1, array, n);
      result= min( result, temp );
      // If we make current array value as the previous array value
      array[i] = array[i - 1];
      temp = cnt -check[i - 1] -check[i] -check[i + 1] +next(i - 1, array, n) +previous(i - 1, array, n) +next(i, array, n) +previous(i, array, n) +next(i + 1, array, n) +previous(i + 1, array, n);

      result= min( result, temp );
      array[i] = curVal;
   }
   return result;
}
int main(){
   // Given Array
   int array[] = { 2, 1, 3, 2, 6 };
   // Getting the size of the given array
   int n = sizeof(array) / sizeof(int);
   // Store minimum count of peaks and troughs by calling the minCountOfPeaksTrougs function
   int res = minCountOfPeaksTrougs(array, n);
   cout << "Minimum Count of Peaks and Troughs are: "<< res;
   return 0;
}

输出

Minimum Count of Peaks and Troughs are: 0

时间和空间复杂度

以上代码的时间复杂度为O(N)，因为我们遍历了数组。

这段代码的空间复杂度为O(N)，因为我们存储了峰值和谷值的计数。

N是数组的大小。

结论

在本教程中，我们实现了一个C++程序，用于在最多一次替换后最小化给定数组中的峰值和谷值的计数。我们实现了一种贪婪的方法。时间复杂度为O(N)，空间复杂度为O(N)。其中N是数组的大小。