当数组中有多个峰值时，如何找到峰值元素？

Question

对于具有单个峰值元素的数组，可以使用二分搜索在 o(logn) 中完成，但是如果数组中存在多个峰值元素，我们应该使用什么方法？

---添加更多信息 ---- 峰值元素是比它的邻居更大的元素，例如，看看下面的数组，

[1,3,20,4,1,0,7,5,2]

其中有 2 个峰值，20 和 7。

我们需要设计一种算法来查找该数组中的峰值元素。

Answer 1

我可能不明白你的问题，因为找到单个峰值可以在 O(logn) 中完成，需要首先对数组进行排序。

我建议您存储一个差异数组，它将生成如下输出：[1,3,20,4,1,0,7,5,2]=> [1, 1,-1,-1,-1, 1,-1,-1]，它只是生成一个大小的数组n - 1并将增加的方向放置在数组中。这可以在 O(n) 单遍中完成。

在第二遍中，您将寻找 [1, -1] 对，这是峰值发生的地方。

如果你想找到开始和结束的峰值，你需要检查开始是否为-1，结束是否为1。

希望这可以帮助。