[LeetCode] LeetCode852. 山脉数组的顶峰索引

题目描述

思路：用二分进行排除不满足条件的元素，最后剩下的元素即为答案

往常我们使用「二分」进行查值，需要确保序列本身满足「二段性」：当选定一个端点（基准值）后，结合「一段满足 & 另一段不满足」的特性来实现“折半”的查找效果。
但本题求的是峰顶索引值，如果我们选定数组头部或者尾部元素，其实无法根据大小关系“直接”将数组分成两段。
但可以利用题目发现如下性质：由于 arr 数值各不相同，因此峰顶元素左侧必然满足严格单调递增，峰顶元素右侧必然不满足。
因此 以峰顶元素为分割点的 arr 数组，根据与 前一元素/后一元素 的大小关系，具有二段性：

• 峰顶元素左侧满足 arr[i−1]<arr[i]arr[i-1] < arr[i]arr[i−1]<arr[i] 性质，右侧不满足
• 峰顶元素右侧满足 arr[i]>arr[i+1]arr[i] > arr[i+1]arr[i]>arr[i+1] 性质，左侧不满足

方法一：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        // 有题目可知:i(0 < i < arr.length - 1) 左闭右闭区间
        int left = 1, right = arr.length - 2;
        while (left <= right) {
            if (left == right) return left;
            int mid = left + (right - left) / 2;
            // mid与mid + 1进行比较,排除不符合的元素
            if (arr[mid] < arr[mid + 1]){ // 在右边找
                left = mid + 1;
            } else if (arr[mid] > arr[mid + 1]) { // 在左边找,但mid可能为峰值
                right = mid;
            } 
        }
        throw new RuntimeException("Error");
    }
}