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

结论 #

不存在比O(n)时间复杂度更高效的解法，遍历数组逐个校验是当前场景下的最优方案。

原因解释 #

• 原版单峰值问题可以用O(logn)的二分法，核心逻辑是只需要找到任意一个峰值，因此可以根据mid和相邻元素的大小关系，直接排除不可能存在目标峰值的半侧数组。
• 但要返回所有峰值的场景下，被排除的半侧数组内仍然可能存在其他峰值，比如数组[1,3,2,5,4,6,1]，如果首次取mid=3（值为5），按单峰值逻辑会排除右半部分，但索引5位置的6也是合法峰值，会被遗漏，因此二分法的剪枝逻辑完全不适用。
• 最坏情况下数组的峰值数量可以达到O(n)级别（比如交错高低的数组[1,2,1,2,1,2,1]峰值有3个，长度为n时峰值数量接近n/2），这种场景下必须遍历所有元素才能保证不遗漏峰值，不可能有比O(n)更低的时间复杂度。

遍历实现（JS，匹配题目示例规则） #

题目示例中峰值定义为必须同时大于左右两侧存在的元素（首尾元素不算峰值），对应实现如下：

var findAllPeakElements = function(nums) {
    const res = []
    const n = nums.length
    // 首尾不可能符合要求，直接从1遍历到n-2即可
    for (let i = 1; i < n - 1; i++) {
        if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) {
            res.push(i)
        }
    }
    return res
}

调用示例：输入[1,2,1,3,5,6,4]，输出[2,5]，完全符合要求。

内容的提问来源于stack exchange，提问作者Joji