📑 题目：162. 寻找峰值

🚀 本题 LeetCode 传送门

题目大意

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。

说明:

• 你的解法应该是 O(logN) 时间复杂度的。

解题思路

• 给出一个数组，数组里面存在多个“山峰”，(山峰的定义是，下标 i 比 i-1、i+1 位置上的元素都要大)，找到这个“山峰”，并输出其中一个山峰的下标。
• 这一题是第 852 题的伪加强版，第 852 题中只存在一个山峰，这一题存在多个山峰。但是实际上搜索的代码是一样的，因为此题只要求随便输出一个山峰的下标即可。思路同第 852 题。

代码

package leetcode
// 解法一 二分
func findPeakElement(nums []int) int {
 if len(nums) == 0 || len(nums) == 1 {
  return 0
 }
 low, high := 0, len(nums)-1
 for low <= high {
  mid := low + (high-low)>>1
  if (mid == len(nums)-1 && nums[mid-1] < nums[mid]) || (mid > 0 && nums[mid-1] < nums[mid] && (mid <= len(nums)-2 && nums[mid+1] < nums[mid])) || (mid == 0 && nums[1] < nums[0]) {
   return mid
  }
  if mid > 0 && nums[mid-1] < nums[mid] {
   low = mid + 1
  }
  if mid > 0 && nums[mid-1] > nums[mid] {
   high = mid - 1
  }
  if mid == low {
   low++
  }
  if mid == high {
   high--
  }
 }
 return -1
}
// 解法二 二分
func findPeakElement1(nums []int) int {
 low, high := 0, len(nums)-1
 for low < high {
  mid := low + (high-low)>>1
  // 如果 mid 较大，则左侧存在峰值，high = m，如果 mid + 1 较大，则右侧存在峰值，low = mid + 1
  if nums[mid] > nums[mid+1] {
   high = mid
  } else {
   low = mid + 1
  }
 }
 return low
}