852. 山脉数组的峰顶索引
题目描述
输入长度为 n 的整数数组 arr，它是山脉数组：元素先严格递增到某个最大值，之后严格递减。
返回最大值（峰顶）所在的下标，下标从 0 开始。
算法的时间复杂度必须是 O(log(n))。
示例 1
输入：arr = [0,1,0] 输出：1
示例 2
输入：arr = [0,2,1,0] 输出：1
示例 3
输入：arr = [0,10,5,2] 输出：1
数据范围
3 <= arr.length <= 10^50 <= arr[i] <= 10^6- 保证
arr是山脉数组。
解题思路
比较 arr[mid] 与右邻 arr[mid+1]：若 arr[mid] < arr[mid+1]，mid 还在上坡，峰顶在 mid 右边，lo = mid + 1；否则 mid 在下坡或就是峰顶，hi = mid。区间收缩到一点即为峰顶。
为什么正确
峰顶下标始终在 [lo, hi] 中。
复杂度分析
时间 O(log n)，空间 O(1)。
易错点
和 mid-1 比较时 mid 可能为 0 而越界；和 mid+1 比较时只要 lo < hi，mid+1 一定合法。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
return loclass Solution {
public int peakIndexInMountainArray(int[] arr) {
int lo = 0, hi = arr.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < arr[mid + 1]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
}class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int lo = 0, hi = (int)arr.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < arr[mid + 1]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
};func peakIndexInMountainArray(arr []int) int {
lo, hi := 0, len(arr)-1
for lo < hi {
mid := (lo + hi) / 2
if arr[mid] < arr[mid+1] {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}var peakIndexInMountainArray = function(arr) {
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < arr[mid + 1]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
};function peakIndexInMountainArray(arr: number[]): number {
let lo = 0, hi = arr.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] < arr[mid + 1]) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}