寻找峰值

发表于

描述
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

  1. 峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
  2. 假设nums[-1]=nums[n]=−∞
  3. 对于所有有效的i都有nums[i] != nums[i+1]

数据范围：
1≤nums.length≤2*105
-231≤nums[i]≤231-1

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

示例1

1
2
3
输入:  [2,4,1,2,7,8,4]
返回:  1
说明:  4和8都是峰值元素，返回4的索引1或者8的索引5都可以

示例2

1
2
3
输入:  [1,2,3,1]
返回:  2
说明:  3 是峰值元素，返回其索引 2

题解

  • 二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇
  • 如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间
  • 如果中间值大于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间
  • 最后区间收尾相遇的点一定就是波峰
寻找峰值.gif 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

/**
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func findPeakElement( nums []int ) int {
    // write code here
    left := 0
    rigth := len(nums) -1
    for left < rigth {
      middle := left + (rigth - left) / 2
      if nums[middle] > nums[middle+1] {
        rigth = middle
      } else {
        left = middle + 1
      }
    }

    return rigth
}