What is the best approach for solving Find Peak Element?

The best approach is using binary search over the valid answer space, which ensures that the solution is both time-efficient and space-efficient.

How does binary search help in the Find Peak Element problem?

Binary search helps by narrowing down the search space to find a peak element in O(log n) time, compared to a brute force approach that would take O(n) time.

Can Find Peak Element have multiple correct answers?

Yes, there can be multiple peaks in the array, and the solution can return any index corresponding to a peak element.

What is the time complexity of the optimal solution for Find Peak Element?

The time complexity of the optimal binary search solution is O(log n), which is much faster than a linear scan of the array.

How does GhostInterview assist with the Find Peak Element problem?

GhostInterview helps by providing practice problems, feedback on binary search techniques, and tips on optimizing solutions for problems like Find Peak Element.

#162

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums ，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。 …

数组二分查找

题目描述

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

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

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

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

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

lightbulb

解题思路

方法一：二分查找

我们定义二分查找的左边界 $left=0$ ，右边界 $right=n-1$ ，其中 $n$ 是数组的长度。在每一步二分查找中，我们找到当前区间的中间元素 $mid$ ，然后比较 $mid$ 与其右边元素 $mid+1$ 的值：

如果 $mid$ 的值大于 $mid+1$ 的值，则左侧存在峰值元素，我们将右边界 $right$ 更新为 $mid$ ；
否则，右侧存在峰值元素，我们将左边界 $left$ 更新为 $mid+1$ 。
最后，当左边界 $left$ 与右边界 $right$ 相等时，我们就找到了数组的峰值元素。

时间复杂度 $O(\log n)$ ，其中 $n$ 是数组 $nums$ 的长度。每一步二分查找可以将搜索区间减少一半，因此时间复杂度为 $O(\log n)$ 。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return left

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Assessing the candidate's understanding of binary search and its application to specific problems.
question_mark
Looking for clarity in explaining why binary search works for this problem, especially with edge cases.
question_mark
Evaluating the candidate's ability to write efficient, optimal code without unnecessary operations.

warning

常见陷阱

外企场景

error
Misunderstanding the concept of a peak at the edges of the array, especially when dealing with virtual boundaries (-∞).
error
Forgetting to check both neighbors during the binary search, potentially missing the peak element.
error
Using a brute-force approach that results in higher time complexity instead of utilizing binary search.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to return all peak elements instead of just one.
arrow_right_alt
Extend the problem to find the global peak that is strictly larger than all elements in the array.
arrow_right_alt
Test variations on arrays with repeated elements and adapt the peak definition accordingly.

help

常见问题

外企场景

继续练习

#167 两数之和 II - 输入有序数组 #154 寻找旋转排序数组中的最小值 II #153 寻找旋转排序数组中的最小值