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

Is there an easy way to find the local maxima in a 1D array?

有没有一种简单的方法可以在一维数组中找到局部最大值?

Let's say I have an array:

假设我有一个数组:

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

I want it to find the 10s and the 4, but ignore the 8 & 6, since those are next to 10s. Mathematically, you could just find where derivative is equal to zero if it were a function. I'm not too sure how to do this in Javascript.

我希望它找到10和4,但忽略8和6,因为那些接近10。在数学上,如果它是一个函数,你可以找到导数等于零的位置。我不太确定如何在Javascript中执行此操作。

7 个解决方案

#1

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])
}

#2

This will return an array of all peaks (local maxima) in the given array of integers, taking care of the plateaus as well:

这将返回给定整数数组中所有峰值(局部最大值)的数组,同时处理高原:

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])   // -> []

Note that the first and last elements of the array are not considered as peaks, because in the context of a mathematical function we don't know what precedes or follows them and so cannot tell if they are peaks or not.

请注意,数组的第一个和最后一个元素不被视为峰值,因为在数学函数的上下文中,我们不知道它们之前或之后是什么,因此无法判断它们是否为峰值。

#3

This code finds local extrema (min and max, where first derivation is 0, and ), even if following elements will have equal values (non-unique extrema - ie. '3' is choosen from 1,1,1,3,3,3,2,2,2)

此代码找到局部极值(min和max,其中第一个推导为0,并且),即使后面的元素具有相等的值(非唯一的极值 - 即从'1,1,1,3,3中选择'3' ,3,2,2,2)

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
      }

 }

#4

How about a simple iteration?

如何进行简单的迭代?

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);

#5

more declarative approach:

更具声明性的方法:

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]

#6

The two situations are when you have a peak, which is a value greater than the previous and greater than the next, and a plateau, which is a value greater than the previous and equal to the next(s) until you find the next different value which must me less.

这两种情况是你有一个峰值,一个大于前一个值的值,大于下一个值,一个高原,一个大于前一个值的值,等于下一个(s),直到找到下一个不同的值必须少的价值。

so when found a plateau, temporary create an array from that position 'till the end, and look for the next different value (the Array.prototype.find method returns the first value that matches the condition ) and make sure it is less than the first plateau value.

因此,当找到一个平台时,从该位置临时创建一个数组直到结束,并查找下一个不同的值(Array.prototype.find方法返回匹配条件的第一个值)并确保它小于第一个高原价值。

this particular function will return the index of the first plateau value.

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

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!)

#7

-1

Math.max is made for that, but it takes a series of arguments instead of an array.

Math.max是为此而制作的,但它需要一系列参数而不是数组。

apply calls a function with arguments passed as an array.

apply调用带有作为数组传递的参数的函数。

Math.max.apply(null, array) does the trick.

Math.max.apply(null,array)可以解决问题。

#1

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])
}

#2