leetcode 852. 山脉数组的峰顶索引（优质解法）

代码：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left=0,right=arr.length-1;
        while (left<right){
            int mid=left+(right-left+1)/2;
            
            if(arr[mid]>arr[mid-1]){
                left=mid;
            }else {
                right=mid-1;
            }
        }
        
        return left;
    }
}

题解：

? ? ? ? 简单分析一下题目的要求，首先题目给出的信息有：

? ? ? ? 1.山脉数组的长度 > = 3,代表每一组数组必定存在一个顶点

? ? ? ? 2.?山脉数组由整数组成

? ? ? ? 3.我们要找到满足?arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]?的下标?i

? ? ? ? 所以数组就呈现如下的结构：

? ? ? ? 比如数组 arr =[1,2,3,2,1] 时，我们要找的顶点就是 3 ，下标为 2

? ? ? ? 我们对上述的数组进行分析，我们可以将数组划分为两个区间【1，2，3】是递增区间，【2，1】是递减区间，在图中的划分就是

? ? ? ? 通过该划分，我们要找的数据就是递增区间中的右边界，当我们在数组中随机选择一个数? ?arr[ i ] ， 如果 arr[ i ] > arr[ i-1 ] ,就代表该数在递增区间，我们便可以大胆排除该数左边的数据（但不能排除该数，因为我们想获得的答案就在递增区间中，我们不能确定该数是否刚好就是我们想要的答案）

????????如果 arr[ i ] <?arr[ i-1 ] ，就代表该数在递减区间，我们便可以大胆排除该数以及该数右边的数据? ?

? ? ? ? 通过上述分析，我们便知道该题具有二段性，所以我们可以用二分法来解决该问题

同样是? arr =[1,2,3,2,1] 的例子

? ? ? ? 将 L 和 R 指针指向左右边界，计算 mid = L +（R- L+1）/2 = 3 ，因为 arr[ mid ] > arr[ mid -1 ],所以 mid 指向的值在递增区间，让 L = mid

1? ? ? ? 2? ? ? ? 3? ? ? ? 2? ? ? ? 1

L? ? ? ? ? ? ? ? ?mid? ? ?? ? ? ? ? ?R

? ? ? ? 计算 mid = 3，此时 arr[ mid ] <?arr[ mid -1 ],所以 mid 指向的值在递减区间，让 R = mid -1

1? ? ? ? 2? ? ? ? 3? ? ? ? 2? ? ? ? 1

? ? ? ? ? ? ? ? ? ? L? ?? ? mid? ? ?R

? ? ? ? 当 L 和 R 指针相遇时代表找到了符合条件的值，返回 L 指针指向的位置即可

1? ? ? ? 2? ? ? ? 3? ? ? ? 2? ? ? ? 1

? ? ? ? ? ? ? ? ? ? L?

? ? ? ? ? ? ? ? ? ? R

? ? ? ? ?