题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
样例
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
算法1
二分查找
时间复杂度
logn
C++ 代码
class Solution {
public:
int findPeakElement(vector<int>& nums) {
// 题目提示时间复杂度O(logn),因此可以考虑是否可以二分
// 经过读题,可知该题属于“左边升序(降序),右边降序(升序),寻找中间值”的二分经典场景
/*
注意题中说到 假设 nums[-1] = nums[n] = -∞ ,
因此存在单调函数的两种情况,这种直接走到边界,返回即可
*/
// 采用循环式二分,以防爆栈
int nLeft = 0, nRight = nums.size() - 1;
while (nLeft <= nRight) {
/*
只有两个元素待比较时,返回最大值即可,
若此处不做特判,则需要将下面计算nMid的式子改为nLeft+((nRight-nLeft+1)>>1),
否则会造成漏判 nRight=nLeft+1 的情况,比如 nLeft=0,nRight=1,nMid=0,则直接进入if判断,会造成漏判和下面的nMid-1越界
*/
if (nLeft == nRight - 1) return nums[nLeft] > nums[nRight] ? nLeft : nRight;
int nMid = nLeft + ((nRight - nLeft) >> 1);
if (nMid == 0 || nMid == nums.size() - 1) return nMid; // 走到边界(包含了size为1的情况),证明答案就是该值,直接返回,以防越界
// 看左边是否小于中间值,右边是否小于中间值
if (nums[nMid - 1] < nums[nMid] && nums[nMid + 1] < nums[nMid])
{
return nMid;
}
// 升序:左边<中间值<右边,则答案应在右边,即修改nLeft=nMid+1
else if (nums[nMid - 1] < nums[nMid] && nums[nMid] < nums[nMid + 1])
{
nLeft = nMid + 1;
}
// 降序:左边>中间值>右边,则答案应在左边,即修改nRight=nMid-1
else
{
nRight = nMid - 1;
}
}
return 0;
}
};
算法2
类似于记录一个大根堆,但题中并没有要求输出序列,因此借用一个变量记录当前的最大值。
如果当前遍历的值大于最大值,则更新最大值。如果当前遍历的值小于最大值,则表示出现了一个峰值,直接返回即可。
时间复杂度
On
C++ 代码
class Solution {
public:
int findPeakElement(vector<int>& nums) {
// 暴力遍历:如果当前值小于记录索引对应的数值,则直接返回记录索引,大则更新记录索引
int nIndex=0;
for(int i=1;i<nums.size();i++)
{
if(nums[i]<nums[nIndex])
{
return nIndex;
}
else
{
nIndex=i;
}
}
return nIndex;
}
};