本文深入探讨了如何在山脉数组中查找其峰值索引。我们将首先介绍一种直观的线性扫描方法，分析其工作原理与局限性，随后重点阐述如何利用二分查找算法在对数时间复杂度内高效地定位峰值，并提供详细的代码实现与注意事项，旨在帮助读者理解并掌握解决此类问题的优化策略。
引言：山脉数组及其峰值索引
在算法领域，”山脉数组”是一种特殊的数组结构，其定义如下：一个数组 arr 被称为山脉数组，如果满足以下条件：
arr.length >= 3。存在某个索引 i，满足 0 < i < arr.length – 1，使得：arr[0] < arr[1] < … < arr[i – 1] arr[i + 1] > … > arr[arr.length – 1] (数组从 i 到结尾严格递减)。
我们的目标是给定一个山脉数组 arr，返回其峰值索引 i。此外，通常要求算法的时间复杂度为 O(log(arr.length))。
方法一：线性扫描法
线性扫描法是一种直观且易于理解的解决方案。由于山脉数组只有一个峰值，且这个峰值是数组中的最大元素，我们可以通过遍历整个数组来找到这个最大值及其对应的索引。
原理
算法从数组的第一个元素开始，依次向后遍历。在遍历过程中，它会维护一个当前找到的最大值 (peakValue) 和该最大值对应的索引 (peakIndex)。每当遇到一个比 peakValue 更大的元素时，就更新 peakValue 和 peakIndex。遍历结束后，peakIndex 即为山脉数组的峰值索引。
示例代码
public class Solution { public static int peakIndexInMountainArray(int[] arr) { // 初始化峰值和峰值索引。 // 由于题目保证arr.length >= 3，且峰值在0 < i < arr.length - 1， // 可以从arr[0]开始，或者确保peakValue初始值足够小。 // 这里的实现从0开始，适用于所有非负数的情况。 int peakValue = 0; int peakIndex = 0; // 遍历数组寻找最大值及其索引 for (int i = 0; i peakValue) { peakValue = value; peakIndex = i; } } return peakIndex; } public static void main(String[] args) { System.out.println("示例 1: " + peakIndexInMountainArray(new int[]{0,1,2})); // 2 (峰值是2，索引2) System.out.println("示例 2: " + peakIndexInMountainArray(new int[]{0,1,0})); // 1 (峰值是1，索引1) System.out.println("示例 3: " + peakIndexInMountainArray(new int[]{0,2,1,0})); // 1 (峰值是2，索引1) System.out.println("示例 4: " + peakIndexInMountainArray(new int[]{0,10,5,2})); // 1 (峰值是10，索引1) System.out.println("示例 5: " + peakIndexInMountainArray(new int[]{0,100,500,2})); // 2 (峰值是500，索引2) }}
复杂度分析
时间复杂度： O(N)，其中 N 是数组的长度。算法需要遍历数组中的所有元素一次。空间复杂度： O(1)，仅使用了常数额外的存储空间来保存 peakValue 和 peakIndex。
局限性
尽管线性扫描法简单直观且易于实现，但它不满足题目通常要求的 O(log(arr.length)) 时间复杂度约束。对于大型数组，其性能会随着数组长度的增加而线性下降。
纳米搜索
纳米搜索：360推出的新一代AI搜索引擎
30 查看详情
方法二：二分查找法
为了满足 O(log(arr.length)) 的时间复杂度要求，我们需要利用二分查找。山脉数组的特性（先严格递增后严格递减）使其非常适合二分查找。
原理
二分查找的核心思想是每次将搜索范围减半。在山脉数组中，我们可以根据当前中间元素 arr[mid] 的值与 arr[mid+1] 的关系来判断峰值位于 mid 的哪一侧：
如果 arr[mid] < arr[mid+1]： 这意味着 mid 位于山脉的上升段。峰值一定在 mid 的右侧。因此，我们将搜索范围的左边界 low 更新为 mid + 1。如果 arr[mid] > arr[mid+1]： 这意味着 mid 位于山脉的下降段，或者 mid 本身就是峰值。峰值可能在 mid 处或 mid 的左侧。因此，我们将搜索范围的右边界 high 更新为 mid。
通过不断缩小搜索范围，low 和 high 最终会汇合到峰值索引。
示例代码
class Solution { public int peakIndexInMountainArray(int[] arr) { int low = 0; // high的初始值可以设置为arr.length - 1。 // 根据山脉数组的定义，峰值不会是最后一个元素（arr.length - 1）， // 且 mid + 1 在循环内部是安全的，不会越界，因为 high 最终会收敛到峰值索引， // 而峰值索引小于 arr.length - 1。 int high = arr.length - 1; // 当 low < high 时继续循环。 // 最终 low 和 high 会汇合到峰值索引。 while (low < high) { // 计算中间索引，防止 low + high 溢出 int mid = low + (high - low) / 2; // 如果 mid 位于上升坡 (arr[mid] < arr[mid+1])， // 峰值在 mid 的右侧，包括 mid+1。 if (arr[mid] arr[mid+1])， // 或者 mid 就是峰值。 // 峰值在 mid 或 mid 的左侧。 else { // arr[mid] > arr[mid + 1] high = mid; } } // 循环结束时，low（或 high，因为它们相等）即为峰值索引 return low; }}
示例分析：arr = [0, 2, 1, 0]
初始化： low = 0, high = 3第一次迭代：mid = 0 + (3 – 0) / 2 = 1`arr[mid] = arr
以上就是山脉数组峰值索引查找：从线性扫描到高效二分查找的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/330193.html
微信扫一扫 
支付宝扫一扫 
