寻找峰值

1. 题目描述

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

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

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

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

2. 思路

1. 暴力
2. 二分

3. 实现

3.1. 暴力

func findPeakElement(nums []int) int {
    for i, num := range nums {
        left := i-1
        right := i+1
        if ( left < 0 || nums[left] < num ) && (right >= len(nums) || nums[right] < num) {
            return i
        }
    }
    return -1
}

func max(a, b int) int {
    if a > b {return a}
    return b
}

3.2. 二分

func findPeakElement(nums []int) int {
    left := 0
    right := len(nums)-1
    /*
    也许很多人看了，还是不懂，图解也只是迷迷糊糊根据答案来，我这里通俗解释以下，这道题，最最最重要的是条件，条件，条件，两边都是负无穷，数组当中可能有很多波峰，也可能只有一个，如果尝试画图，就跟股票信息一样，没有规律，如果根据中点値判断我们的二分方向该往何处取， 这道题还有只是返回一个波峰。你这样想，中点所在地方，可能是某座山的山峰，山的下坡处，山的上坡处，如果是山峰，最后会二分终止也会找到，关键是我们的二分方向，并不知道山峰在我们左边还是右边，送你两个字你就明白了，爬山（没错，就是带你去爬山），如果你往下坡方向走，也许可能遇到新的山峰，但是也许是一个一直下降的坡，最后到边界。但是如果你往上坡方向走，就算最后一直上的边界，由于最边界是负无穷，所以就一定能找到山峰，总的一句话，往递增的方向上，二分，一定能找到，往递减的方向只是可能找到，也许没有
    */
    for left < right {
        mid := left + (right-left) >> 1
        if nums[mid] < nums[mid+1] {
            left = mid+1
        }else {
            right=mid
        }
    }
    return left
}

4. 参考

• 画解算法：162. 寻找峰值 - 寻找峰值 - 力扣（LeetCode）