162. 寻找峰值

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

题目

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]

Output: 2

Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]

Output: 5

Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• nums[i] != nums[i + 1] for all valid i.

题目大意

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

解题思路

要求算法在 O(log n) 的时间内完成，可以使用二分查找来解决。

在每一步二分查找中，可以找到中间元素 mid，然后与其相邻的元素 mid-1 和 mid+1 进行比较。如果 nums[mid] > nums[mid-1] 且 nums[mid] > nums[mid+1]，则 mid 即为峰值元素的位置。如果 nums[mid-1] > nums[mid]，则峰值元素必然在 mid 的左侧；如果 nums[mid+1] > nums[mid]，则峰值元素必然在 mid 的右侧。

通过不断缩小搜索范围，最终可以找到一个峰值元素的位置。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
	let left = 0;
	let right = nums.length - 1;
	while (left < right) {
		const mid = Math.floor((left + right) / 2);
		if (nums[mid] > nums[mid + 1]) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
};

相关题目

题号	标题	题解	标签	难度
852	山脉数组的峰顶索引	[✓]	数组 二分查找
1901	寻找峰值 II		数组 二分查找 矩阵
2137	通过倒水操作让所有的水桶所含水量相等 🔒		数组 二分查找
2210	统计数组中峰和谷的数量		数组
2951	找出峰值		数组 枚举