leetCode 852. 山脉数组的峰顶索引

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

一、遍历数组直接查找

时间复杂度 O(n)

let ans = arr[0]
for(let a = 0; a < arr.length; a++){
    ans = Math.max(ans,arr[a])
}
1
2
3
4

二、 二分查找

时间复杂度O(log(n))

/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function(arr) {
    let left = 0,right = arr.length-1,ans = 0
    while(left <= right){
        let mid = Math.floor((right - left) / 2) + left
        if(arr[mid + 1] < arr[mid]){
            ans = mid // 每次记录最大值
            right = mid-1
        }else{
            left = mid+1
        }
    }

    return ans


};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20