刷题使我快乐，满脸开心.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}

欢迎关注公众号交流更多题目~