571，山脉数组的峰顶索引

Original 博哥数据结构和算法 2022-05-19

This is the best summer I've ever had.

这是我度过最好的一个夏天。

问题描述

来源：LeetCode第852题

难度：简单

符合下列属性的数组arr称为山脉数组：

1，arr.length>=3

2，存在i（0<i<arr.length-1）使得：

arr[0]<arr[1]<...arr[i-1]<arr[i]
arr[i]>arr[i+1]>...>arr[arr.length-1]

给你由整数组成的山脉数组arr，返回任何满足arr[0]<arr[1]<...arr[i-1]<arr[i]>arr[i+1]>...>arr[arr.length-1]的下标i。

示例 1：

输入：arr = [0,1,0]
输出：1

示例 2：

输入：arr = [0,2,1,0]
输出：1

示例 3：

输入：arr = [0,10,5,2]
输出：1

示例 4：

输入：arr = [3,4,5,1]
输出：2

示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

提示：

3 <= arr.length <= 10^4
0 <= arr[i] <= 10^6
题目数据保证arr是一个山脉数组

直接查找

之前讲过475，有效的山脉数组，而这题是让找出山脉数组的峰顶索引，我们看提示的最后一条是题目数据保证arr是一个山脉数组，也就是山脉数组一定是存在的，所以不需要判断，直接查找即可。

山脉数组是先上升然后在下降，如果当前元素比右边挨着的小，说明开始下降了，那么当前元素就是山脉数组的峰顶，只需要返回他的索引即可

1public int peakIndexInMountainArray(int[] arr) {
2    for (int i = 0; i < arr.length - 1; ++i)
3        if (arr[i] > arr[i + 1])
4            return i;
5    return 0;
6}

二分法解决

山脉数组前面部分是升序的，后面部分是降序的，所以也可以使用二分法，用中间的值和他的下一个比较（根据题中对山脉数组的定义，以及提示的最后一条，所以数组中挨着的两个数字不可能相同，要么比下一个小，要么比下一个大）

如果比下一个小，说明还处在上升阶段，缩小查找的范围到[mid+1，right]
如果比下一个大，说明处在下降阶段，缩小查找范围到[left，mid]

 1public int peakIndexInMountainArray(int[] arr) {
 2    int left = 0;
 3    int right = arr.length - 1;
 4    while (left < right) {
 5        int mid = left + (right - left) / 2;
 6        //如果mid比他后面的小，说明是在上升，缩小范围
 7        if (arr[mid] < arr[mid + 1])
 8            left = mid + 1;
 9        else
10            right = mid;
11    }
12    return left;
13}

或者还可以写成递归的形式

 1public int peakIndexInMountainArray(int[] arr) {
 2    return helper(arr, 0, arr.length - 1);
 3}
 4
 5public int helper(int[] arr, int left, int right) {
 6    int mid = left + (right - left) / 2;
 7    //比左右两个都大，说明是峰顶，直接返回
 8    if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
 9        return mid;
10    //mid指向的值处在爬升阶段
11    if (arr[mid] < arr[mid + 1])
12        return helper(arr, mid + 1, right);
13    return helper(arr, left, mid);
14}