162.寻找峰值(Medium)

题目描述

查找数据中峰值元素，峰值元素是值大于左右相邻值的元素。返回元素的位置

样例

Input: [1,2,3,1]
Output: 2
# 3是峰值元素，返回其索引 2

题目解析

方法一：线性扫描

遍历数组元素，查找值是大于左右相邻元素

线性扫描的时间复杂度是 $O(n)$，空间复杂度是 $O(1)$

方法二：二分搜索

粗看本题不满足二分查找的有序条件。二分查找是通过左右指针逼近的方式查找 峰值。

将中间值与右元素进行比较

• 当中间值大于右元素，满足单调减：right = mid
• 当中间值小于等于右元素，递增，肯定不满足条件： left = mid + 1

Python代码示例

线性扫描

线性扫描有两种实现方式

1. 对边界特殊处理

2. 利用单调性处理：

   默认数组是单调递增，一旦出现右边的值小的话，就找到索引。对于最后一个元素单独处理。

# 边界处理
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if (i == len(nums) - 1 or  nums[i] > nums[i+1]) and \
               (i == 0 or nums[i] > nums[i-1]):
               return i
        return len(nums) - 1
      
# 单调性写法
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return i
        return len(nums) - 1

二分查找1：找到 mid > 右 最靠右的值

# 模板2 二分查找 mid > 右 最靠右的值
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 
# 模板1 二分查找, 使用ans记录
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        ans = 0
        while left <= right:
            mid = (left + right) >> 1
            if mid == len(nums) - 1 or nums[mid] > nums[mid + 1]:  # 这里可能取最右值
                ans = mid
                right = mid - 1 
            else:
                left = mid + 1
        return ans

二分查找2：找到 左 < mid 最靠左的值

# 模板2 找到 左 < mid 最靠左的值
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) >> 1
            if mid == 0 or nums[mid] > nums[mid - 1]:
                left = mid + 1
            else:
                right = mid 
        return left - 1
# 模板1 
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        ans = 0
        while left <= right:
            mid = (left + right) >> 1
            if mid == 0 or nums[mid] > nums[mid - 1]:
                ans = mid
                left = mid + 1
            else:
                right = mid - 1
        return ans