852. 山脉数组的峰顶索引

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

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 是一个山脉数组

解题思路

1. 使用二分查找：可以通过二分查找来高效找到这个峰值：

   • 设置 left 为数组的起始索引，right 为数组的结束索引。
   • 在每次迭代中计算中间索引 mid。

2. 判断中间元素：

   • 如果 arr[mid] 是峰值，则直接返回 mid。
   • 如果 arr[mid] 大于其左侧元素而小于其右侧元素，说明峰值在右侧，因此将 left 移动到 mid。
   • 如果 arr[mid] 小于其左侧元素，说明峰值在左侧，因此将 right 移动到 mid。

3. 循环直到找到峰值：继续迭代，直到找到峰值索引。

4. 返回结果：当 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+	🔴	🀄️ 🔗