介绍

给定一个整数数组 arr[] 。任务是找出给定数组中所有局部最小值（local minima）和局部最大值（local maxima）的下标。如果一个元素 arr[x] 小于它的两个邻居，我们称之为是一个局部最小值，局部最大值同理。例如：

Input: arr = [100, 180, 260, 310, 40, 535, 695]
Output:
Points of local minima: 0 4 
Points of local maxima: 3 6

思路：在给定的数组 arr [] 上进行迭代，并检查数组中的每个元素在其相邻元素中是否最小或最大。如果它是最小的，那么它就是局部最小值，如果它是最大的，那么它就是局部最大值。

实现

JavaScript

// Function to find all the local maxima and minima in the given array arr[]
function findLocalMaximaMinima(n, arr) {
    // Empty vector to store points of local maxima and minima
    let mx = [], mn = [];
 
    // Checking whether the first point is local maxima or minima or none
    if (arr[0] > arr[1]) mx.push(0);
    else if (arr[0] < arr[1]) mn.push(0);
 
    // Iterating over all points to check local maxima and local minima
    for(let i = 1; i < n - 1; i++) {
      // Condition for local minima
      if ((arr[i - 1] > arr[i]) && (arr[i] < arr[i + 1])) mn.push(i);
      // Condition for local maxima
      else if ((arr[i - 1] < arr[i]) && (arr[i] > arr[i + 1])) mx.push(i);
    }
 
    // Checking whether the last point is local maxima or minima or none
    if (arr[n - 1] > arr[n - 2]) mx.push(n - 1);
    else if (arr[n - 1] < arr[n - 2]) mn.push(n - 1);
 
    return {mn, mx}
}

分治法：寻找第一个局部最大值。

/**
 * [LocalMaxima](https://www.geeksforgeeks.org/find-indices-of-all-local-maxima-and-local-minima-in-an-array/) is an algorithm to find relative bigger numbers compared to their neighbors
 *
 * Notes:
 * - works by using divide and conquer
 * - the function gets the array A with n Real numbers and returns the local max point index (if more than one exists return the first one)
 *
 * @complexity: O(log(n)) (on average )
 * @complexity: O(log(n)) (worst case)
 */
const findMaxPointIndex = (array, rangeStartIndex, rangeEndIndex, originalLength) => {
  // find index range middle point
  const middleIndex = rangeStartIndex + parseInt((rangeEndIndex - rangeStartIndex) / 2)

  // handle array bounds
  if ((middleIndex === 0 || array[middleIndex - 1] <= array[middleIndex]) && (middleIndex === originalLength - 1 || array[middleIndex + 1] <= array[middleIndex])) return middleIndex
  // 首个局部最大值在左边
  if (middleIndex > 0 && array[middleIndex - 1] > array[middleIndex]) return findMaxPointIndex(array, rangeStartIndex, (middleIndex - 1), originalLength)
  return findMaxPointIndex(array, (middleIndex + 1), rangeEndIndex, originalLength)
}

const LocalMaximomPoint = (A) => findMaxPointIndex(A, 0, A.length - 1, A.length)

分治法：寻找局部最大值的数量。

/**
 * [NumberOfLocalMaximumPoints](https://www.geeksforgeeks.org/find-indices-of-all-local-maxima-and-local-minima-in-an-array/) is an algorithm to find relative bigger numbers compared to their neighbors
 *
 * Notes:
 * - like the other similar local maxima search function find relative maxima points in array but doesn't stop at one but returns total point count
 * - runs on array A of size n and returns the local maxima count using divide and conquer methodology
 *
 * @complexity: O(n) (on average )
 * @complexity: O(n) (worst case)
 * @flow
 */

// check if returned index is a local maxima
const IsMaximumPoint = (array, index) => {
  // handle array bounds
  // array start
  if (index === 0) return array[index] > array[index + 1]
  // array end
  if (index === array.length - 1) return array[index] > array[index - 1]
  // handle index inside array bounds
  return array[index] > array[index + 1] && array[index] > array[index - 1]
}

const CountLocalMaximumPoints = (array, startIndex, endIndex) => {
  // stop check in divide and conquer recursion
  if (startIndex === endIndex) return IsMaximumPoint(array, startIndex) ? 1 : 0
  // handle the two halves
  const middleIndex = parseInt((startIndex + endIndex) / 2)
  return CountLocalMaximumPoints(array, startIndex, middleIndex) + CountLocalMaximumPoints(array, middleIndex + 1, endIndex)
}

const NumberOfLocalMaximumPoints = (A) => CountLocalMaximumPoints(A, 0, A.length - 1)

扩展

TrappingRainWater

参见：TrappingRainWater [接住雨水] | Fancy DSA

参考

• Find indices of all local maxima and local minima in an Array - GeeksforGeeks (opens new window)