峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。
数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[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。说明:
你的解法应该是 O(logN) 时间复杂度的。
如果一个题目,可以简单到用复杂度O(n)的方式解决,但题目要求复杂度为O(logN)复杂度,这种情况下基本上就直接考虑使用二分查找。
但原始二分查找要求数组是有序的,很显然,这个题目中数组并无序。所以我们要转化一下思路,二分就是折半嘛,如何才能折半查找呢?
对于任何一个数组中的元素,如果它大于右边的元素,那么这个元素肯定处于一个递减区间里,所以对于这个递减区间的峰值,肯定在这个元素的左侧(包括它自己)。
这个性质很隐蔽,但也是解决这个问题的最重要的性质,如果能想明白这个,问题就迎刃而解了。
我们采用折半查找的思想,取中间元素,如果中间元素大于右边元素,那么再比较和左边元素,如果也大于左边,那么它就是峰值元素。如果不大于左边元素,那么说明峰值在它左侧,我们再对它左侧区间进行查找,直到找到峰值即可。
1 | func findPeakElement(nums []int) int { |