也就是局部最大,可以采用二分法来实现。当然局部最小也一样。
峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
类似这种局部最小和局部最大的问题。我们均可以采用二分的方法来解决,并不一样非要有序才可使用二分进行搜索。特定条件的无序也是可以的。简单来说二分查找的目的就是舍弃一般可以抛弃的降低查找次数。
首先我们先对情况进行分析,首先判断两个端点是否为峰值,如果是则返回;如果不是,借助一下高数中的拉格朗日定理的思想。则两端均具有一个向上的趋势,因此中间必定存在一个峰值的拐点。
则对于中点可以分为四种情况,
class Solution {
public int findPeakElement(int[] nums) {
int len = nums.length;
int L = 0;
int R = len -1;
if(len == 1){
return 0;
}
if(nums[0]>nums[1])
{
return L;
}
if(nums[len-1] > nums[len-2]){
return R;
}
int mid;
do{
mid = L + ((R-L)>>1);
if(nums[mid]>nums[mid-1] && nums[mid] > nums[mid+1])
{
return mid;
}else if(nums[mid - 1]>nums[mid] && nums[mid] > nums[mid+1])
{
R = mid;
}else if(nums[mid-1] < nums[mid] && nums[mid] < nums[mid+1]) {
L = mid;
}else
{
L = mid;
}
}while(L<R);
return -1;// 可有可无,返回个-1,代表失败吧
}
}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/Y_peak/article/details/120315578
内容来源于网络,如有侵权,请联系作者删除!