郑州网站建设方案报价能去百度上班意味着什么

注意

• 题目只要求找到一个峰值就可以了。
• nums[-1]和nums[n]这两个位置是负无穷，也就是说，除了数组的位置之外，其它地方都是负无穷。
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

方法一

遍历整个数组，找到最高的那个点。时间复杂度O(n)

func findPeakElement(nums []int) int {maxIndex := 0for i := range nums {if nums[i] > nums[maxIndex] {maxIndex = i}}return maxIndex
}

方法二

• 二分法，其实看到O(logn)，很容易就可以想到二分法。

• 二分法，分开了之后，mid是在中间的，有可能是在上坡，也有可能是在下坡，也可能是在峰值，峰值的话，最后二分终止的时候，也会找到的。

  至于选择哪一边呢？其实就按爬山来看就行了。如果是爬到上坡的话，那一定就是有峰值的，但是如果是下坡的话，后面有可能有峰值，也有可能是负无穷。

• 因为题目说的是-1和n位置是负无穷，所以只要找到上坡就行，找到上坡就一定会有解。

func findPeakElement(nums []int) int {l, r := 0, len(nums)-1for l < r {mid := l + (r - l)/2if nums[mid] > nums[mid + 1] {			// 题目规定了nums[i] != nums[i + 1]，所以可以不用考虑等于号的情况r = mid							// 左边大，说明左边有峰值，那就往左边靠} else {l = mid + 1				// 右边大，说明右边有峰值，那就往右边靠}}return l
}