什么是山脉数组？
在深入探讨峰值查找方法之前，首先需要明确山脉数组的定义。一个数组 arr 被称作山脉数组，如果它满足以下条件：
- arr.length >= 3：数组的长度至少为3。
- 存在一个索引 i，满足 0
- arr[0]
- arr[i] > arr[i+1] > ... > arr[arr.length-1]：数组从索引 i 到结尾是严格递减的。
简而言之，山脉数组就像一座山，先上升到最高点（峰值），然后下降。我们的目标就是找到这个最高点（峰值）的索引 i。
直观的线性扫描方法
最直接的思路是遍历整个数组，找到其中最大的元素，并记录其索引。由于山脉数组的特性，最大的元素必然是峰值。
实现原理
- 初始化一个变量 peakValue 来存储当前找到的最大值，以及 peakIndex 来存储其对应的索引。
- 遍历数组中的每一个元素。
- 如果当前元素的值大于 peakValue，则更新 peakValue 为当前元素的值，并更新 peakIndex 为当前元素的索引。
- 遍历结束后，peakIndex 即为山脉数组的峰值索引。
示例代码
public class Solution {
public static int peakIndexInMountainArray(int[] arr) {
int peakValue = 0; // 初始化峰值，通常取数组第一个元素或0
int peakIndex = 0;
// 假设数组长度至少为3，且arr[0]总是小于arr[1]，所以可以从0开始比较
// 更严谨的做法是初始化为arr[0]，peakIndex=0
if (arr.length > 0) {
peakValue = arr[0];
}
for (int i = 0; i < arr.length; i++) {
int value = arr[i];
if (value > peakValue) {
peakValue = value;
peakIndex = i;
}
}
return peakIndex;
}
public static void main(String[] args) {
System.out.println("Set 1: " + peakIndexInMountainArray(new int[]{0,1,2})); // 2
System.out.println("Set 2: " + peakIndexInMountainArray(new int[]{0,1,0})); // 1
System.out.println("Set 3: " + peakIndexInMountainArray(new int[]{0,2,1,0})); // 1
System.out.println("Set 4: " + peakIndexInMountainArray(new int[]{0,10,5,2})); // 1
System.out.println("Set 5: " + peakIndexInMountainArray(new int[]{0,100,500,2})); // 2
}
}复杂度分析
- 时间复杂度: 算法需要遍历整个数组一次，因此时间复杂度为 O(N)，其中 N 是数组的长度。
- 空间复杂度: 算法只使用了常数个额外变量，因此空间复杂度为 O(1)。
虽然线性扫描方法简单易懂且实现方便，但它不满足题目中通常要求的 O(log(arr.length)) 时间复杂度约束。对于大规模数据，我们需要更高效的算法。
高效的二分查找方法 (O(logN))
为了达到 O(logN) 的时间复杂度，我们应该考虑使用二分查找算法。山脉数组的特性（先递增后递减）使其具有局部单调性，这正是二分查找能够发挥作用的场景。
为什么选择二分查找？
山脉数组可以看作是两个有序数组的拼接：一个升序部分和一个降序部分。峰值是这两个部分的交界点。二分查找的核心思想是每次将搜索区间减半，通过比较中间元素来判断峰值可能位于哪一半，从而快速逼近目标。
核心思想与实现逻辑
在二分查找中，我们通常关注 mid 索引处的元素及其相邻元素 arr[mid+1]。
- 初始化 low = 0 和 high = arr.length - 1 作为搜索区间的边界。
- 在 low
- 计算 mid = low + (high - low) / 2，以防止整数溢出。
- 比较 arr[mid] 和 arr[mid+1]：
- 如果 arr[mid]
- 如果 arr[mid] > arr[mid+1]：这说明 mid 位于山脉的下降段，或者 mid 本身就是峰值。峰值可能在 mid 处，也可能在 mid 的左侧。因此，我们将搜索区间的上界 high 更新为 mid。
- 当循环结束时 (low == high)，low（或 high）就是峰值所在的索引。
示例代码
public class Solution {
public int peakIndexInMountainArray(int[] arr) {
int low = 0;
int high = arr.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
// 如果mid在上升段，峰值在mid的右侧
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
}
// 如果mid在下降段，或者mid就是峰值
// 峰值可能在mid或mid的左侧
else {
high = mid;
}
}
// 当low == high时，找到了峰值索引
return low;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println("Test Case [0,1,2]: " + sol.peakIndexInMountainArray(new int[]{0,1,2})); // 2
System.out.println("Test Case [0,1,0]: " + sol.peakIndexInMountainArray(new int[]{0,1,0})); // 1
System.out.println("Test Case [0,2,1,0]: " + sol.peakIndexInMountainArray(new int[]{0,2,1,0})); // 1
System.out.println("Test Case [0,10,5,2]: " + sol.peakIndexInMountainArray(new int[]{0,10,5,2})); // 1
System.out.println("Test Case [0,100,500,2]: " + sol.peakIndexInMountainArray(new int[]{0,100,500,2})); // 2
}
}复杂度分析
- 时间复杂度: 每一次迭代，搜索区间都会减半，因此时间复杂度为 O(logN)，其中 N 是数组的长度。
- 空间复杂度: 算法只使用了常数个额外变量，因此空间复杂度为 O(1)。
这种二分查找方法能够满足题目对时间复杂度的严格要求，是解决此类问题的最优方案。
注意事项
- 数组长度: 题目明确指出山脉数组的长度 arr.length >= 3。这意味着在进行 mid+1 操作时，我们不需要担心 mid+1 会超出数组的有效索引范围（除非 mid 已经是 arr.length - 1，但二分查找的逻辑会避免这种情况，因为 high 不会取到 arr.length - 1 并在 mid 处进行 mid+1 比较，它会在 high 缩减到峰值时停止）。
- 保证是山脉数组: 题目通常会保证给定的数组是一个合法的山脉数组，因此我们不需要额外编写代码来验证数组是否符合山脉数组的定义。这简化了问题，我们可以直接应用上述算法。
- 二分查找边界: while (low
总结
查找山脉数组的峰值索引是一个经典的算法问题，它展示了如何利用数据结构的特性来优化算法性能。
- 线性扫描方法简单直观，时间复杂度为 O(N)，适用于对性能要求不高的场景或小型数据集。
- 二分查找方法则利用了山脉数组的单调性，将时间复杂度优化到 O(logN)，是处理大规模数据和满足高性能要求的首选方案。
理解并掌握二分查找的原理和正确实现方式，对于解决这类具有特定结构的数据查找问题至关重要。在实际开发中，根据具体的需求和约束选择合适的算法，是提高程序效率的关键。
