algorithm - 找到一个数组的所有局部最大值，该数组增加或减少 1

Question

如何找到运行 O(k log n) 次的算法，其中 k 是局部最大值的数量，n 是数组的大小 例如:

[1,2,3,4,5,6,5,6,7,8,7]

Answer 1

作为一个粗略的想法，您可以使用最大值的数量(显然之前已知)作为附加参数。检查数组的中间值是否为局部最大值(如果元素数量为偶数，则检查中间值左边或右边的值)。如果不是局部最大值，则在左子数组或右子数组中搜索局部最大值。类似 C# 的伪代码的表述如下；如果需要极大值的位置，则需要额外进行一些指标计算。

List<int> Input;           // input array
List<int> Maxima;          // output for the maxima
int k;                     // num of local maxima

void SearchMaxima(List<int> iList, int NumOfMaxima)
{
   if (0 == iList.Count() || 0 == NumOfMaxima)
   {
     // do nothing
   }
   else
   {
      if (Middle point of iList is local Maximum)
      {
          Store middle point of iList to MaximaPositions
          SearchMaxima(left half of iList w/o middle point, NumOfMaxima - 1);
          SearchMaxima(right half of iList w/o middle point, NumOfMaxima - 1);
      }
      else
      {
          SearchMaxima(left half of iList w/o middle point, NumOfMaxima);
          SearchMaxima(right half of iList w/o middle point, NumOfMaxima);
      }
   }
}