【LeetCode】162. 寻找峰值

一、题目描述

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

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[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。

说明:
你的解法应该是 O(logN) 时间复杂度的。

二、解题思路 & 代码

2.1 线性扫描

利用连续的两个元素 nums[j] 和nums[j+1] 不会相等

遍历 numsnums 数组。每当我们遇到数字nums[i]，只需要检查它是否大于下一个元素 nums[i+1] 即可判断 nums[i] 是否是峰值。可以通过分别讨论问题的全部三种可能情况来理解本方法的思路。

1. 情况 1. 所有的数字以降序排列。
2. 情况 2. 所有的数字以升序排列。
3. 情况 3. 峰值出现在中间某处。

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

复杂度分析

时间复杂度 : O(n)。 我们对长度为 n 的数组 nums 只进行一次遍历。
空间复杂度 : O(1)。 只使用了常数空间。

2.2 递归二分查找

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        def search(nums, l, r):
            if (l == r):
                return l
            mid = (l + r) // 2
            if (nums[mid] > nums[mid + 1]):
                return search(nums, l, mid)
            return search(nums, mid + 1, r)
        return search(nums, 0, len(nums) - 1)

复杂度分析

时间复杂度 : O(logN)
空间复杂度 : O(logN)

2.3 迭代二分查找

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

复杂度分析

时间复杂度 : O(logN)
空间复杂度 : O(1)

参考：

1. LeetCode官方题解