在一个一维数组中寻找局部最大值

Question

有没有一种简单的方法来寻找一维数组中的局部最大值？

假设我有一个数组：

[ 0,
  1,
  10, <- max
  8,  <- (ignore)
  3,
  0,
  0,
  4,
  6,  <- (ignore)
  10, <- max
  6,  <- (ignore)
  1,
  0,
  0,
  1,
  4,  <- max
  1,
  0 ]

我希望它能找到10和4，但忽略8和6，因为它们紧挨着10。数学上，如果它是一个函数，你可以找到导数等于零的地方。我不太确定如何在Javascript中实现这一点。

- user499054

---

你想要值还是它们的索引？ - dee-see

Answer 1

该函数将返回给定整数数组中所有高峰（局部最大值）的数组，同时处理高原情况：

function findPeaks(arr) {
  var peak;
  return arr.reduce(function(peaks, val, i) {
    if (arr[i+1] > arr[i]) {
      peak = arr[i+1];
    } else if ((arr[i+1] < arr[i]) && (typeof peak === 'number')) {
      peaks.push(peak);
      peak = undefined;
    }
    return peaks;
  }, []);
}

findPeaks([1,3,2,5,3])   // -> [3, 5]
findPeaks([1,3,3,3,2])   // -> [3]
findPeaks([-1,0,0,-1,3]) // -> [0]
findPeaks([5,3,3,3,4])   // -> []

请注意，数组的第一个和最后一个元素不被视为峰值，因为在数学函数的上下文中，我们不知道它们之前或之后的情况，所以无法确定它们是否是峰值。

- Alexander Makarenko

---

findPeaks([-1, 0, -1]) returns [] instead of [0] - le_m

findPeaks([1, 2, NaN, 3, 1]) 返回 [2] 而不是 []。 - le_m

@le_m 我已更新我的解决方案以正确处理零作为峰值的情况。 - Alexander Makarenko

@le_m 输入数组假定仅包含整数，因此不会检查NaN值等。如有需要，请随意添加它们。 - Alexander Makarenko

Answer 2

maxes = []
for (var i = 1; i < a.length - 1; ++i) {
    if (a[i-1] < a[i] && a[i] > a[i+1])
        maxes.push(a[i])
} 

- tohava

---

相当简单而整洁的解决方案。然而，如果你的最大值是平台型的（例如3,4,5,6,6,6,3,2），则这种方法无法奏效。 - Michael Stauffer

它还会忽略第一个和最后一个元素。仅推送索引为i的元素，其中i在[1...n-2]范围内，n是输入数组的长度。例如，a=[3,2,1,2,3]将产生空数组作为输出。 - Sidmeister

这种方法在实践中存在相当多的问题。因为最小/最大值的定义可以在不同的时间窗口内定义，而此代码片段仅将该窗口设置为大小1。 - windmaomao

Answer 3

两种情况是峰值和高原。峰值是指比前一个值和后一个值都大的数值，而高原是指比前一个值大且等于后一个或多个连续相同值的数值，直到找到下一个不同的数值为止，该数值必须小于高原第一个数值。

因此，当发现高原时，从该位置开始临时创建一个数组，查找下一个不同的值（Array.prototype.find 方法返回满足条件的第一个值），并确保它小于第一个高原值。

此特定函数将返回第一个高原值的索引。

function pickPeaks(arr){
  return arr.reduce( (res, val, i, self) => {
    if(
      // a peak when the value is greater than the previous and greater than the next
      val > self[i - 1] && val > self[i + 1] 
      || 
      // a plateau when the value is greater than the previuos and equal to the next and from there the next different value is less
      val > self[i - 1] && val === self[i + 1] && self.slice(i).find( item =>  item !== val ) < val 
    ){
      res.pos.push(i);
      res.peaks.push(val);
    }
    return res;
  }, { pos:[],peaks:[] } );
}

console.log(pickPeaks([3,2,3,6,4,1,2,3,2,1,2,3])) //{pos:[3,7],peaks:[6,3]}
console.log(pickPeaks([-1, 0, -1])) //{pos:[1],peaks:[0]}
console.log(pickPeaks([1, 2, NaN, 3, 1])) //{pos:[],peaks:[]}
console.log(pickPeaks([1, 2, 2, 2, 1])) //{pos: [1], peaks: [2]} (plateau!)

- Julian

---

console.log(pickPeaks([1, 2, NaN, 3, 1])) //{pos:[],peaks:[]} -> 你不认为这个输出是错误的吗？ - Sultan Ali

Answer 4

这段代码可以找到局部极值点（最小值和最大值，其中一阶导数为0），即使后续元素具有相等的值（非唯一极值点 - 例如，从1,1,1,3,3,3,2,2,2中选择'3'）。请保留html标签。

var GoAsc  = false;      //ascending move
var GoDesc = false;      //descending move
var myInputArray = [];
var myExtremalsArray = [];
var firstDiff;

for (index = 0; index < (myArray.length - 1); index++) {
    //(myArray.length - 1) is because not to exceed array boundary, 
    //last array element does not have any follower to test it

  firstDiff = ( myArray[index] - myArray[index + 1] );

   if ( firstDiff > 0 )   { GoAsc  = true;  }
   if ( firstDiff < 0 )   { GoDesc = true;  }

   if ( GoAsc === true && GoDesc === true )  {  
        myExtremalsArray.push(myArray[index]);
        GoAsc  = false ;     
        GoDesc = false;     
        //if firstDiff > 0 ---> max
        //if firstDiff < 0 ---> min
      }

 }

- user3473058

Answer 5

怎么样，来个简单的迭代？

var indexes = [];
var values = [0,1,10,8,3,0,0,4,6,10,6,1,0,0,1,4,1,0];
for (var i=1; i<values.length-1; i++)
    if (values[i] > values[i-1] && values[i] > values[i+1])
        indexes.push(i);

- barak manos

Answer 6

更加声明式的方法：

const values = [3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3];

const findPeaks = arr => arr.filter((el, index) => {
  return el > arr[index - 1] && el > arr[index + 1]
});
  
console.log(findPeaks(values)); // => [6, 3]

- vitkon

Answer 7

一个Python实现，有几个要点

• 避免使用reduce函数，使算法更易于理解
• 第一个和最后一个元素被视为峰值（这可能是一个要求，例如在面试中）
• 高原上的所有值都会被加起来
• 可以从高原开始或结束

def findPeaks(points: List[int]) -> List[int]:
    peaks, peak = [], []

    if points[0] >= points[1]:  # handle first
        peak.append(points[0])

    for i in range(1, len(points)):
        prv = points[i - 1]
        cur = points[i]

        if cur > prv:  # start peak
            peak = [cur]
        elif cur == prv:  # existing peak (plateau)
            peak.append(cur)
        elif cur < prv and len(peak):  # end peak
            peaks.extend(peak)
            peak = []

    if len(peak) and len(peak) != len(points):  # ended on a plateau
        peaks.extend(peak)

    return peaks

if __name__ == "__main__":
    print(findPeaks([1, 2, 3, 4, 5, 4, 3, 2, 1]))   # [5]
    print(findPeaks([1, 2, 1, 2, 1]))               # [2, 2]
    print(findPeaks([8, 1, 1, 1, 1, 1, 9]))         # [0, 6]
    print(findPeaks([1, 1, 1, 1, 1]))               # []
    print(findPeaks([1, 6, 6, 6, 1]))               # [6, 6, 6]

- Jack

Answer 8

const values = [3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3];

const findMinimas = arr => arr.filter((el, index) => {
  return el < arr[index - 1] && el < arr[index + 1]
});
  
console.log(findMinimas(values)); // => [2, 1, 1]

const findMinimumIndices = arr => arr.map((el, index) => {
  return el < arr[index - 1] && el < arr[index + 1] ? index : null
}).filter(i => i != null);
  
console.log(findMinimumIndices(values)); // => [1, 5, 9]

- 井上智文