0852. 山脉数组的峰顶索引【中等】
1. 📝 题目描述
给定一个长度为 n 的整数 山脉 数组 arr，其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
txt
输入：arr = [0,1,0]
输出：11
2
2
示例 2：
txt
输入：arr = [0,2,1,0]
输出：11
2
2
示例 3：
txt
输入：arr = [0,10,5,2]
输出：11
2
2
提示：
3 <= arr.length <= 10^50 <= arr[i] <= 10^6- 题目数据 保证
arr是一个山脉数组
2. 🎯 s.1 - 二分查找
c
int peakIndexInMountainArray(int* arr, int arrSize) {
int lo = 1, hi = arrSize - 2;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (arr[mid] < arr[mid + 1]) lo = mid + 1;
else hi = mid;
}
return lo;
}1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
js
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function (arr) {
let lo = 1,
hi = arr.length - 2
while (lo < hi) {
const mid = (lo + hi) >> 1
if (arr[mid] < arr[mid + 1]) lo = mid + 1
else hi = mid
}
return lo
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
py
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
lo, hi = 1, len(arr) - 2
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] < arr[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
- 时间复杂度：
- 空间复杂度：
算法思路：
- 二分查找：若
arr[mid] < arr[mid+1]，峰在右侧；否则峰在左侧或就是 mid