引言：山脉数组及其峰值索引
在算法领域，"山脉数组"是一种特殊的数组结构，其定义如下： 一个数组 arr 被称为山脉数组，如果满足以下条件：
- arr.length >= 3。
- 存在某个索引 i，满足 0
- arr[0]
- arr[i] > 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 < 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("示例 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)) 时间复杂度约束。对于大型数组，其性能会随着数组长度的增加而线性下降。
方法二：二分查找法
为了满足 O(log(arr.length)) 的时间复杂度要求，我们需要利用二分查找。山脉数组的特性（先严格递增后严格递减）使其非常适合二分查找。
原理
二分查找的核心思想是每次将搜索范围减半。在山脉数组中，我们可以根据当前中间元素 arr[mid] 的值与 arr[mid+1] 的关系来判断峰值位于 mid 的哪一侧：
- 如果 arr[mid] 这意味着 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]) {
low = mid + 1;
}
// 如果 mid 位于下降坡 (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
