当前位置 博文首页 > 数据结构和算法：LeetCode 852. 山脉数组的峰顶索引
截止到目前我已经写了 600多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
之前讲过475，有效的山脉数组，而这题是让找出山脉数组的峰顶索引，我们看提示的最后一条是题目数据保证arr是一个山脉数组，也就是山脉数组一定是存在的，所以不需要判断，直接查找即可。
山脉数组是先上升然后在下降，如果当前元素比右边挨着的小，说明开始下降了，那么当前元素就是山脉数组的峰顶，只需要返回他的索引即可
public int peakIndexInMountainArray(int[] arr) {
for (int i = 0; i < arr.length - 1; ++i)
if (arr[i] > arr[i + 1])
return i;
return 0;
}
public int peakIndexInMountainArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
//如果mid比他后面的小，说明是在上升，缩小范围
if (arr[mid] < arr[mid + 1])
left = mid + 1;
else
right = mid;
}
return left;
}
或者还可以写成递归的形式
public int peakIndexInMountainArray(int[] arr) {
return helper(arr, 0, arr.length - 1);
}
public int helper(int[] arr, int left, int right) {
int mid = left + (right - left) / 2;
//比左右两个都大，说明是峰顶，直接返回
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
return mid;
//mid指向的值处在爬升阶段
if (arr[mid] < arr[mid + 1])
return helper(arr, mid + 1, right);
return helper(arr, left, mid);
}
