跳至主要內容

162. 寻找峰值


162. 寻找峰值

🟠   🔖  数组 二分查找  🔗 力扣open in new window LeetCodeopen in new window

题目

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-1mid+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山脉数组的峰顶索引[✓]数组 二分查找🟠🀄️open in new window 🔗open in new window
1901寻找峰值 II数组 二分查找 矩阵🟠🀄️open in new window 🔗open in new window
2137通过倒水操作让所有的水桶所含水量相等 🔒数组 二分查找🟠🀄️open in new window 🔗open in new window
2210统计数组中峰和谷的数量数组🟢🀄️open in new window 🔗open in new window
2951找出峰值数组 枚举🟢🀄️open in new window 🔗open in new window