Блог

Похоже на этот вопрос с кодом литкода https://leetcode.com/problems/find-peak-element/ но возвращаемый результат должен быть массивом индексов для всех пиков или локального максимума

Напр.

Учитывая такой массив [1,2,1,3,5,6,4] , мне нужно вернуть [2, 5]

Если мы вернем только одно пиковое число, мы можем просто использовать двоичный поиск, чтобы один раз удалить половину массива. Вот мое решение

 var findPeakElement = function(nums) {
    let left = 0, right = nums.length - 1
    
    while(left < right) {
        const mid = Math.floor((left   right) / 2)
        if(nums[mid] > nums[mid   1]) {
            right = mid
        } else {
            left = mid   1
        }
    }
    
    
    return right
};
 

Но теперь вопрос в том, чтобы вернуть все индексы к локальным максимальным числам. Я не могу придумать другого способа, кроме как перебирать массив и проверять число по одному, чтобы увидеть, больше ли оно предыдущего числа и следующего числа.

Вам действительно нужно просканировать весь массив, и на это потребуется O (n) время. Простое доказательство состоит в том , что при попытке [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, ..., 2, 1, 2] половина ваших значений будет локальными максимумами, поэтому любой алгоритм, который проверяет это, потребует как минимум n / 2 операций (какого-то рода).

Вот довольно простая версия, которая сообщает обо всех пиках, с отдельной обработкой для первого и последнего индексов и общей обработкой для остальных. Это предполагает, что вам нужны только настоящие вершины, а не плато. Если вам нужны индексы плато, вам придется заменить некоторые < > знаки / на <= / >= .

 const localMaxima = (ns) => [
  ... (ns [0] > ns [1] ? [0] : []),
  ... Array .from ({length: ns.length - 1}, ((_, i) => i   1)) 
        .filter ((i) => ns [i - 1] < ns [i] amp;amp; ns [i   1] < ns [i]),
  ... (ns [ns .length - 1] > ns [ns .length - 2] ? [ns .length - 1] : [])
]

console .log (localMaxima ([1, 2, 1, 3, 5, 6, 4])) //=> [1, 5]
//                             ^           ^
console .log (localMaxima ([8, 5, 7, 5, 3, 0, 9])) //=> [0, 2, 6]
//                          ^     ^           ^
console .log (localMaxima ([2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2])) //=> [0, 2, 4, 6, 8, 10]
//                          ^     ^     ^     ^     ^     ^ 

 .as-console-wrapper {max-height: 100% !important; top: 0} 

Обратите внимание, что возвращается первый пример [1, 5] . Было [2, 5] ли в вопросе просто опечаткой?

Обновить

Комментарий с просьбой сделать это «более читабельным».

Есть абсолютно одна вещь, которую я должен был сделать. Я встроил range здесь функцию. Для этого не было никаких причин. Это гораздо более читабельно при использовании отдельной функции. ( range это простая функция для возврата целого диапазона. Например range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] .)

Использование этого вместо этого приводит к тому, что для меня является вполне читаемой версией:

 const range = (lo, hi) => Array .from ({length: hi - lo   1}, (_, i) => lo   i)

const localMaxima = (ns) => [
  ... (ns [0] > ns [1] ? [0] : []),
  ... range (1, ns.length - 2) .filter ((i) => ns [i - 1] < ns [i] amp;amp; ns [i   1] < ns [i]),
  ... (ns [ns .length - 1] > ns [ns .length - 2] ? [ns .length - 1] : [])
]

 

Однако я не думаю, что об этом спрашивают. Я думаю, что запрошенный код может выглядеть примерно так:

 const localMaxima = (ns) => {
  const includeStart = ns [0] > ns [1]
  const includeEnd = ns [ns.length - 1] > ns [ns .length -2]
  const intermediates = range (0, ns .length - 2)
    .filter ((i) => ns [i - 1] < ns [i] amp;amp; ns [i   1] < ns [i])
  if (includeStart) intermediates .unshift (0)
  if (includeEnd) intermediates .push (ns .length - 1)
  return intermediates
}
 

Но мне это совсем не нравится. Я изо всех сил стараюсь работать с неизменяемыми данными, unshift и push звонки » и » ужасны для моих глаз.

Вероятно, самое близкое, к чему я мог бы подойти и все еще смотреть на себя в зеркало, — это

 const localMaxima = (ns) => {
  const includeStart = ns [0] > ns [1]
  const includeEnd = ns [ns.length - 1] > ns [ns .length -2]
  const intermediates = range (0, ns .length - 2)
    .filter ((i) => ns [i - 1] < ns [i] amp;amp; ns [i   1] < ns [i])
  const beginning = includeStart ? [0] : []
  const ending = includeEnd ? [ns .length - 1] : []
  return beginning .concat (intermediates) .concat (ending)
}
 

Я также не большой поклонник этих одноразовых назначений переменных, но в таких языках, как JS, их иногда трудно избежать. По крайней мере, они все еще здесь const . Я бы не стал заменять это:

   const beginning = includeStart ? [0] : []
 

с этой альтернативой

   let beginning
  if (includeStart) {
    beginning = [0]
  } else {
    beginning = []
  }
 

так что, если вам просто не нравятся условные операторы (троичные), мы, вероятно, никогда не увидимся с глазу на глаз!

Я бы в любой день предпочел свой range пострефакторинг этим версиям. Но читабельность в глазах смотрящего, и, возможно, это последнее сделало бы некоторых счастливыми.

Насколько я могу судить, ваш подход верен. Вам действительно нужно посмотреть на три значения (текущее, предыдущее и следующее), чтобы определить, является ли число локальным максимумом.

Абстрагируясь на мгновение от JavaScript и просто размышляя об этом математически, нахождение локального максимума непрерывной функции (которая является приближенной моделью для этого массива целых чисел) означает нахождение точек, в которых ее первая производная (т. е. ее градиент) равна 0, а ее вторая производная (т. е. градиент градиента начальной функции) отрицательна. То есть точки, в которых функция плоская и изгибается вниз.

Чтобы найти производную функции численно, вам нужно посмотреть на две точки функции. То же самое касается поиска второй производной — вам нужно посмотреть на две точки производной функции. Каждая из этих двух точек в производной функции была рассчитана на основе двух точек в исходной функции, но одна из этих точек является общей, поэтому, по сути, вам нужно посмотреть на три точки в исходной функции, чтобы найти вторую производную.

Однако имейте в виду, что вам не всегда нужно будет проводить два сравнения. Если число меньше, чем предыдущее, конечно, вам не нужно проверять следующее число, потому что вы уже знаете, что не нашли локальный максимум. Однако вам может потребоваться рассмотреть крайний случай, когда одно и то же число появляется несколько раз подряд, и независимо от того, должно ли каждое из них считаться локальным максимумом.