852. 山脉数组的峰顶索引

阅读量50次

题目

符合下列属性的数组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 = [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

提示：

invalid image (图片无法加载)

思路

二分查找,找到一个同时大于左右两边整数的值，它的下标就是要找的i的值

代码

语言：Java

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        while (low < high) {
            // 计算中间值
            mid = low + (high - low) / 2;  //防止int溢出
            if(mid == 0 || mid == arr.length-1) {
                break;
            }
            if( (arr[mid] < arr[mid-1]) && (arr[mid] > arr[mid+1])) {
                // mid下标对应的值大于左右两边的值，命中
                break;
            }
            if(arr[mid] > arr[mid-1]) {
                // mid下标对应的值大于左边值，查找的值在mid左边
                high = mid;
            } else if(arr[mid] < arr[mid+1]) {
                // mid下标对应的值大于右边值，查找的值在mid右边
                low = mid;
            }
        }
        return mid;
    }
}