刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/find-peak-element/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

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

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

你必须实现时间复杂度为 O(log 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。

提示：

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

思路

感觉碰到好几次了，时间复杂度要求给出提示之类的。
不过有个问题需要解决，那就是二分之后该选哪边？需要找到一种能够确定哪边一定有峰值的方法来，所以我画了个图，尝试分析：

用 left 和 right 的值判断往那边走（这个思路是错的，这里只是为了说明思路）

开始我是想用 left 和 right 的值（与mid的比较）来判断应该往那边走，因为如图所示，如果 right 值 5 比 mid 值 3 大，那么在右边就一定存在一个峰值，要么在中途，要么在 right 位置上
但是很快就发现一个极端反例: 如果两边都跟 mid 值相等，那么就不一定存在峰值了

用 mid 相邻值判断往那边走

虽然上面的思路不通，但是总觉得往高处走这个想法是正确的，然后就有了如图这个思路：

如果 mid + 1 比 mid 值大，那么在往右半边走的时候，会是一个上升的趋势，而在不会有相邻值相等的限制条件下就意味着:

• 要么右半边一直上升，right位置是峰值
• 要么右半边会有那么一个位置，从上升趋势变成下降趋势，也就是所谓的峰值了！

所以：如果 mid 相邻的值中存在比mid大的值，那么在这半边一定存在峰值

至此，上代码

代码

func findPeakElement(nums []int) int {
    // 先判断第一个和最后一个元素
    n := len(nums)
    if n == 1 || nums[0] > nums[1] {
        return 0
    } else if nums[n-1] > nums[n-2] {
        return n - 1
    }

    // 二分法，判断mid元素
    left, right, mid := 0, n-1, 0
    for left <= right {
        mid = (left + right) / 2
        // 0 和 n-1 之前已经判断了，不用单独处理了，只要防止越界就好
        if mid != 0 && mid != n-1 && nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1] {
            return mid
        }
        // 往上坡走一定有峰值，往下坡走不一定有峰值
        if mid != n-1 && nums[mid] < nums[mid+1] {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}