LeetCode-每日一题 剑指 Offer II 069. 山峰数组的顶部 [Java实现] [极速]

符合下列属性的数组 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 ，即山峰顶部。

提示：

• 3 <= arr.length <= 104
• 0 <= arr[i] <= 106
• 题目数据保证 arr 是一个山脉数组

示例 1：

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

        说是双指针，其实也相当于二分。因为题目保证输入数据成山峰形状，即一定存在一升序区间 [0, i]与一降序区间 [i, length-1]。我们计算每次中间指针的位置并根据中间指针处于升序 / 降序区间对双指针进行移动。

    public int peakIndexInMountainArray(int[] arr) {
        int left = 0, right = arr.length-1;
        while (left != right) {
            if (right-left == 1) return arr[left] < arr[right] ? right : left;
            int middle = (left+right) / 2; // i-1 < i < i+1
            if ((middle > 1 && arr[middle] > arr[middle-1]) || (middle < arr.length-1 && arr[middle] < arr[middle+1])) {
                left = middle;
            } else if ((middle > 1 && arr[middle] < arr[middle-1]) || (middle < arr.length-1 && arr[middle] > arr[middle+1])) {
                // i-1 > i > i+1
                right = middle;
            }
        }
        return left;
    }

                ​​​​​​​        ​​​​​​​        ​​​​​​​