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] = -∞.

Example:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example:

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.

问题

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

给定一个从0开始索引的整数数组 nums，找到一个峰值元素并返回其索引。如果数组包含多个峰值，返回任何一个峰值的索引即可。

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

解决方案 1

线性扫描法

Approach 1 / 方法 1

The simplest approach to find a peak element is to iterate through the array and compare each element with its neighbors. If an element is greater than both of its neighbors, it is a peak element.

最简单的找到峰值元素的方法是遍历数组，并将每个元素与其相邻元素进行比较。如果一个元素大于其左右相邻的元素，则它是峰值元素。

Implementation / 实现

python

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(1, len(nums) - 1):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                return i
        return 0 if nums[0] >= nums[-1] else len(nums) - 1

Explanation / 解释

1. Iterate Through the Array / 遍历数组

   for i in range(1, len(nums) - 1):

   • English: We start iterating from the second element to the second last element of the array.
   • Chinese: 我们从数组的第二个元素开始遍历，到倒数第二个元素结束。

2. Check if the Current Element is a Peak / 检查当前元素是否为峰值

   if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
      return i

   • English: If the current element is greater than both its left and right neighbors, return its index.
   • Chinese: 如果当前元素大于其左侧和右侧的相邻元素，则返回其索引。

3. Edge Case Handling / 边界情况处理

   return 0 if nums[0] >= nums[-1] else len(nums) - 1

   • English: If no peak is found during the iteration, return the index of the first or last element, whichever is larger.
   • Chinese: 如果在遍历过程中没有找到峰值，返回第一个或最后一个元素的索引，返回较大的那个。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the length of the array. In the worst case, we may need to traverse the entire array.
• Space Complexity / 空间复杂度: O(1), as no extra space is required other than a few variables.

Key Concept / 关键概念

• Linear Scan / 线性扫描: This approach simply checks each element to find a peak, ensuring that no peak is missed.
• 线性扫描: 这种方法简单地检查每个元素以找到峰值，确保不会遗漏任何峰值。

解决方案 2

二分查找法

Approach 2 / 方法 2

A more efficient way to find a peak element is to use a binary search approach. The idea is to check the middle element and decide which side to move towards based on its neighbors. If the middle element is not a peak, move towards the side where a peak is more likely to be found.

一种更高效的找到峰值元素的方法是使用二分查找。其思想是检查中间元素，并根据其相邻元素决定向哪一侧移动。如果中间元素不是峰值，则向更有可能找到峰值的一侧移动。

Implementation / 实现

python

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1

        return left

Explanation / 解释

1. Initialize Pointers / 初始化指针

   left, right = 0, len(nums) - 1

   • English: We initialize left and right pointers to the beginning and end of the array, respectively.
   • Chinese: 我们将 left 和 right 指针分别初始化为数组的起始和结束位置。

2. Perform Binary Search / 执行二分查找

   while left < right:
      mid = (left + right) // 2

   • English: We perform a binary search by calculating the middle index mid.
   • Chinese: 我们通过计算中间索引 mid 来执行二分查找。

3. Compare the Middle Element with its Right Neighbor / 将中间元素与其右侧相邻元素进行比较

   if nums[mid] > nums[mid + 1]:
      right = mid
   else:
      left = mid + 1

   • English: If the middle element is greater than its right neighbor, a peak must be on the left side, so we move the right pointer to mid. Otherwise, we move the left pointer to mid + 1.
   • Chinese: 如果中间元素大于其右侧相邻元素，则峰值必须在左侧，因此我们将 right 指针移动到 mid。否则，我们将 left 指针移动到 mid + 1。

4. Return the Peak Index / 返回峰值索引

   return left

   • English: When the left pointer meets the right pointer, we have found a peak, and we return its index.
   • Chinese: 当 left 指针与 right 指针相遇时，我们已经找到了一个峰值，并返回其索引。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(log n), where n is the length of the array. The binary search approach divides the array in half each time, leading to logarithmic time complexity.
• Space Complexity / 空间复杂度: O(1), as no extra space is required other than a few variables.

Key Concept / 关键概念

• Binary Search / 二分查找: This approach efficiently finds a peak element by continually narrowing down the search space, ensuring optimal performance.
• 二分查找: 这种方法通过不断缩小搜索空间，高效地找到峰值元素，确保了最佳性能。

Summary / 总结

• English: Both linear scan and binary search approaches are effective for finding a peak element in an array. The linear scan method is straightforward but less efficient, while the binary search method is optimized for performance.
• Chinese: 线性扫描和二分查找方法都能有效地在数组中找到峰值元素。线性扫描方法简单直接，但效率较低，而二分查找方法则优化了性能。

Tips / 提示

• English: Use the binary search approach for larger arrays where performance is a concern.
• Chinese: 对于较大的数组，在性能受到关注时使用二分查找方法。

Solution Template for Similar Questions / 提示

• English: Consider both linear and binary search approaches depending on the problem’s constraints and the size of the input array.
• Chinese: 根据问题的限制和输入数组的大小，考虑线性和二分查找方法。

5 More Similar Questions / 推荐5问题

1. LeetCode 852. Peak Index in a Mountain Array
2. LeetCode 74. Search a 2D Matrix

3. [LeetCode 153. Find Minimum

   in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/)

4. LeetCode 34. Find First and Last Position of Element in Sorted Array
5. LeetCode 33. Search in Rotated Sorted Array

Recommended Resources / 推荐资源

• English: Practice both linear and binary search methods on similar problems to solidify your understanding and enhance your problem-solving skills.
• Chinese: 在类似问题上练习线性和二分查找方法，以巩固理解并提高问题解决能力。

Find Peak Element - Leetcode 162 - Python by NeetCodeIO