[LeetCode] 162. Find Peak Element

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
-231 <= nums[i] <= 231 - 1
nums[i] != nums[i + 1] for all valid i.

寻找峰值。

峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

给一个数组，数组满足条件nums[i] ≠ nums[i+1]，求数组峰值的下标。这个题的👎多于👍，估计是因为峰值不止一个吧，我做的时候也踩了坑。
思路是用二分法，因为题目要求时间复杂度是 log 级别。根据左右指针计算中间位置 m，并比较 m 与 m+1 的值，如果 m 较大，则左侧存在峰值，r = m，如果 m + 1 较大，则右侧存在峰值，l = m + 1。

复杂度

时间O(logn)
空间O(1)

代码

Java实现

class Solution {
	public int findPeakElement(int[] nums) {
		int start = 0;
		int end = nums.length - 1;
		while (start + 1 < end) {
			int mid = start + (end - start) / 2;
			// 峰值可能在mid左侧
			if (nums[mid] > nums[mid + 1]) {
				end = mid;
			}
			// 峰值在mid右侧
			else {
				start = mid;
			}
		}
		if (nums[start] > nums[end]) {
			return start;
		}
		return end;
	}
}

JavaScript实现

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

相关题目

162. Find Peak Element
852. Peak Index in a Mountain Array
1095. Find in Mountain Array