题目

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

给定一个输入数组 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。

方案一（迭代）

func findPeakElement(nums []int) int {
    var before, next = math.Inf(-1), math.Inf(-1)
    for i, num := range nums {
        _nums := float64(num)
        if i > 0 {
            before = float64(nums[i - 1])
        }
        if i < len(nums) - 1 {
            next = float64(nums[i + 1])
        } else {
            next = math.Inf(-1)
        }

        if _nums > before && _nums > next {
            return i
        }
    }

    return -1
}

• 时间复杂度

方案二（二分查找）

func findPeakElement(nums []int) int {
    if len(nums) == 0 {return -1}

    var left, right, length = 0, len(nums) - 1, len(nums)
    var before, current, next = math.Inf(-1), math.Inf(-1), math.Inf(-1)
    for left <= right {
        var mid = (left + right) / 2

        current = float64(nums[mid])
        if mid > 0 {
            before = float64(nums[mid - 1])
        }
        if mid == length - 1 {
            next = math.Inf(-1)
        } else {
            next = float64(nums[mid + 1])
        }

        // 通过图形可以更好的看出来，波段图
        if current > before && current < next { // 在上升阶段
            left = mid + 1
        } else if current < before && current > next { // 在下降阶段
            right = mid - 1
        } else if current < before && current < next { // 在谷底，此时说明最少有两个峰值，向左向右均可
            left = mid + 1
        }else {
            return mid
        }
    }

    return -1
}

• 时间复杂度

方案三（leetcode）

func findPeakElement(nums[]int) int {
    // 特殊情况
    n := len(nums)
    if n==0 {return -1}
    if n==1 {return 0}
    if nums[0]>nums[1] {return 0} // 第一个是峰值
    if nums[n-1]>nums[n-2] {return n-1} // 最后一个是峰值

    // 一般情况
    l, r, mid := 0, n-1, 0
    for l<=r {
        mid = l + (r-l)/2
        if (mid==0 || nums[mid]>nums[mid-1]) && (mid==n-1 || nums[mid]>nums[mid+1]) {
            // 包含了三种可能：
            // mid=0且nums[0]>nums[1]
            // mid=n-1且nums[n-2]<nums[n-1]
            // 0<mid<n-1 且 nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1]
            return mid
        } else if mid>0 && nums[mid]<nums[mid-1] {
            r = mid - 1
        } else if mid<n-1 && nums[mid]<nums[mid+1] {
            l = mid + 1
        }
    }
    return mid        // 这里返回mid
}

• 注意特殊情况

  方案四（模板三）

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if not nums:
            return -1

        if len(nums) == 1:
            return 0
        if nums[0] > nums[1]: # 第一个是峰值
            return 0
        if nums[-1] > nums[-2]: # 最后一个是峰值
            return len(nums) - 1

        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid - 1] < nums[mid] > nums[mid + 1]:
                return mid
            elif nums[mid] >= nums[mid - 1]:
                left = mid
            else:
                right = mid

        # 尾处理
        if nums[left - 1] < nums[left] > nums[left + 1]:
            return left
        if nums[right - 1] < nums[right] > nums[right + 1]:
            return right
        return -1

原文

https://leetcode-cn.com/explore/learn/card/binary-search/210/template-ii/841/