162. Find Peak Element

162. Find Peak Elementopen 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-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;
};

162. Find Peak Element

# 162. Find Peak Elementopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

162. Find Peak Elementopen in new window

题目

题目大意

解题思路

代码

相关题目