JavaScript 算法：如何找到数组中的所有局部最大值

Question

类似于这个 leetcode 问题 https://leetcode.com/problems/find-peak-element/ 但 returned 结果应该是所有峰值或局部最大值的索引数组

例如

给定一个像这样的数组 [1,2,1,3,5,6,4]，我需要 return [2, 5]

如果我们只return一个峰数，我们可以只用二分查找一次消去一半的数组。这是我的解决方案

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

但现在的问题是要求 return 所有索引到本地最大数字。除了遍历数组并一个一个地检查数字以查看它是否大于其前一个数字和下一个数字之外，我想不出任何其他方法。

Answer 1

据我所知，你的做法是正确的。您确实需要查看三个值（当前值、上一个值和下一个值）以确定数字是否为局部最大值。

暂时将其从 JavaScript 中抽象出来，并从数学上考虑它，找到连续函数的局部最大值（这是该整数数组的近似模型）意味着找到位于其中它的一阶导数（即它的梯度）为0，它的二阶导数（即初始函数梯度的梯度）为负。即函数平坦、向下弯曲的点。

要从数值上求函数的导数，您需要查看函数上的两个点。寻找二阶导数也是如此——您需要查看导数函数上的两个点。导数函数中的那两个点分别基于原始函数中的两个点计算，但其中一个点是共享的，因此基本上您需要查看原始函数中的三个点才能找到二阶导数。

请记住，您并不总是需要进行两次比较。如果一个数字小于之前的数字，当然你不需要检查下一个数字，因为你已经知道你没有找到局部最大值。但是，您可能需要考虑连续多次出现相同数字的极端情况，以及它们中的每一个是否都应算作局部最大值。

Answer 2

您必须扫描整个数组，这将花费 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] && 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}

注意第一个例子returns [1, 5]。问题中的 [2, 5] 只是一个错字吗？

更新

要求使本文“更具可读性”的评论。

我绝对应该做一件事。我在这里内联了一个 range 函数。没有理由这样做。使用单独的函数时可读性更高。（range 是 return 整数范围的简单函数。例如 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] && 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] && 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] && 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 = []
  }

因此，如果您只是不喜欢条件运算符（三元组），我们可能永远不会达成共识！

我非常愿意在任何一天对这些版本进行 post-range 重构。但是可读性是仁者见仁智者见智的，也许这最后一个会让一些人高兴。

JavaScript 算法：如何找到数组中的所有局部最大值

JavaScript algorithms: how do I find all local max in an array

javascript

algorithm

binary-search

更新