852. 山脉数组的峰顶索引
852. 山脉数组的峰顶索引
题目
You are given an integer mountain array arr
of length n
where the values increase to a peak element and then decrease.
Return the index of the peak element.
Your task is to solve it in O(log(n))
time complexity.
Example 1:
Input: arr = [0,1,0]
Output: 1
Example 2:
Input: arr = [0,2,1,0]
Output: 1
Example 3:
Input: arr = [0,10,5,2]
Output: 1
Constraints:
3 <= arr.length <= 10^5
0 <= arr[i] <= 10^6
arr
is guaranteed to be a mountain array.
题目大意
给定一个长度为 n
的整数 山脉 数组 arr
,其中的值递增到一个 峰值元素 然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 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^5
0 <= arr[i] <= 10^6
- 题目数据 保证
arr
是一个山脉数组
解题思路
使用二分查找:可以通过二分查找来高效找到这个峰值:
- 设置
left
为数组的起始索引,right
为数组的结束索引。 - 在每次迭代中计算中间索引
mid
。
- 设置
判断中间元素:
- 如果
arr[mid]
是峰值,则直接返回mid
。 - 如果
arr[mid]
大于其左侧元素而小于其右侧元素,说明峰值在右侧,因此将left
移动到mid
。 - 如果
arr[mid]
小于其左侧元素,说明峰值在左侧,因此将right
移动到mid
。
- 如果
循环直到找到峰值:继续迭代,直到找到峰值索引。
返回结果:当
left
与right
重合时,left
就是峰值的索引。
复杂度分析
- 时间复杂度:
O(log n)
,其中n
是数组的长度,每次都将搜索范围缩小一半,使用了二分查找的策略。 - 空间复杂度:
O(1)
,只使用常数级的空间来存储变量,而不随输入规模而变化。
代码
/**
* @param {number[]} arr
* @return {number}
*/
var peakIndexInMountainArray = function (arr) {
let left = 0;
right = arr.length - 1;
while (left < right) {
let mid = ((right + left) / 2) | 0;
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
// arr[mid] 就是峰值
return mid;
} else if (arr[mid] > arr[mid - 1] && arr[mid + 1] > arr[mid]) {
// 峰值在右侧
left = mid;
} else {
// 峰值在左侧
right = mid;
}
}
return left;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
162 | 寻找峰值 | [✓] | 数组 二分查找 | |
1095 | 山脉数组中查找目标值 | 数组 二分查找 交互 | ||
1671 | 得到山形数组的最少删除次数 | [✓] | 贪心 数组 二分查找 1+ |