一、题目

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

• arr.length >= 3
• 存在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[i] - arr[i+``1``]大于0，也就是检测到下降的趋势，那么最大值的坐标就为i

2）二分法

要进一步提高查询的效率，可以使用二分法。
设立头尾两个指针s和e，让mid=(s + e)/2，对arr[mid]和arr[mid-1]进行判断（目标是找到下降段的第一个下标），看arr[i]是否处于上升段：

• 属于上升段，arr[mid]-arr[mid-1]>0，则s=mid+1
• 属于下降段，arr[mid]-arr[mid-1]<0，则e=mid

最后，s-1为所求的最高点坐标

三、代码

1）暴力法

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] - arr[i+1] > 0) {
                return i;
            }
        }
        return arr.length - 1;
    }
}

时间复杂度为O(n)，空间复杂度为O(1)

2）二分法

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

时间复杂度为O(logn)，空间复杂度为O(1)