二分查找
解题思路
arr 是山脉数组，左侧山脉是递增序列，右侧山脉是递减序列；
根据
arr[mid] < arr[mid + 1]判断是左侧山脉，则说明需要收缩左侧指针，这样越来越靠近山顶；根据
arr[mid] > arr[mid + 1]判断是右侧山脉，则说明需要收缩右侧指针，这样越来越靠近山顶；
复杂度
-
时间复杂度：
O(logn) -
空间复杂度：
O(1)
代码实现
var peakIndexInMountainArray = function (arr) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = (left + right) >>> 1;
if (arr[mid] < arr[mid + 1]) { // 左侧山脉序列是递增的
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
36.有效的数独
上一篇
评论
