题目描述
峰值定义为比左右相邻元素大的元素。
给定一个数组 nums
,保证 nums[i] ≠ nums[i+1]
,请找出该数组的峰值,并返回峰值的下标。
数组中可能包含多个峰值,只需返回任意一个即可。
假定 nums[-1] = nums[n] = -∞
。
样例1
输入:nums = [1,2,3,1]
输出:2
解释:3是一个峰值,3的下标是2。
样例2
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:数组中有两个峰值:1或者5,返回任意一个即可。
算法
(二分) $O(\log n)$
首先题目保证了相邻的元素都不相同,我们可以比较nums[mid]
与nums[mid + 1]
的大小关系看能不能推断出答案在哪。
如果nums[mid] < nums[mid + 1]
,那么在[mid + 1, r]
这个区间内一定存在一个峰值。因为如果该区间是单调递增的那么nums[r]
就是峰值,如果不是单调递增的那么第一个出现下降的点就是峰值。
如果nums[mid] > nums[mid + 1]
,那么在[l, mid]
这个区间内一定存在一个峰值。因为从mid
到l
这一段如果是单调递增的那么nums[l]
就是峰值,不过不是那么第一个出现下降的点就是峰值。
注意这里mid + 1
并不会越界,因为计算mid
是左偏的或者说是向下取整的,那么mid
最大时区间为[r - 1, r]
,此时mid
为r - 1
,mid + 1
是r
,并不会越界。
C++ 代码
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[mid + 1]) l = mid + 1;
else r = mid;
}
return l;
}
};
这个能过,另一个yxc Time limit exceeded!