描述
给定一个长度为n的数组nums，请找到峰值并返回索引。数组可能包含多个峰值，在这种情况下，返回任何位置。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于或不等于
2.假设 nums[-1] = nums[n] = ?∞
3.对所有有效的 i 都有 nums[i] != nums[i 1]
4.你可以用O(logN)实现这个问题的时间复杂性吗？
数据范围：
1≤nums.length≤2×10^5
?2^31<=nums[i]<=2^31?1
如果输入[2,4,1,2,7,8,4]，将形成两个山峰，一个是索引1，峰值4，另一个是索引5，峰值8，如下图所示：
示例1
输入：
[2]
返回值：
1
说明：
4和8都是峰值元素，可以返回4索引1或8索引5
示例2
输入：
[1,2,3,1]
返回值：
2
说明：
3 是峰值元素，返回其索引 2
方法一(暴力遍历)
时间复杂度o(n)
空间复杂度o(1)
/** * 已指定代码中的类名、方法名、参数名，请勿修改，直接返回方法规定的值 * * * @param nums int整形一维数组 * @param numsLen int nums数组长度 * @return int整型 * * C语言声明定义全局变量请添加static，防止重复定义 */ int find(int*nums,int start){ int end=start 2; if(nums[start]<nums[start 1]&&nums[start 1]>nums[end]){ return start 1; } else{ return -1; } } int findPeakElement(int* nums, int numsLen ) { // write code here if(numsLen==2){ //数组中只有两个值 if(nums[0]>nums[1]) return 0; else return 1; } if(numsLen==1){ ///数组只有一个值 return 0; } else{ if(nums[0]>nums[1]){ //处理第一值 return 0; } for(int i=0;i<numsLen-3;i ){ int index=find(nums,i); ///三组比较 if(index!=-1){ return index; } } if(nums[numsLen-1]>nums[numsLen-2]){ ///处理倒数第一值 return numsLen-1; } } return -1; /* //两个端点值是-∞(而且元素不重复)，我只需要一直找最大的值，那么这个值一定是峰值 int idx=0; for(int i=1;i<numsLen;i ){ if(nums[i]>nums[idx]){ idx=i; } } return idx; */ }/** * 已指定代码中的类名、方法名、参数名，请勿修改，直接返回方法规定的值 * * * @param nums int整形一维数组 * @param numsLen int nums数组长度 * @return int整型 * * C语言声明定义全局变量请添加static，防止重复定义 */ int findPeakElement(int* nums, int numsLen ) { // write code here //两个端点值是-∞(而且元素不重复)，我只需要一直找到最大值，那么这个值一定是峰值 int idx=0; for(int i=1;i<numsLen;i ){ if(nums[i]>nums[idx]){ idx=i; } } return idx; }方法二:(二分法)
时间复杂度o(logn),空间复杂度o(1)
import java.util.*; public class Solution { /** * 已指定代码中的类名、方法名、参数名，请勿修改，直接返回方法规定的值 * * * @param nums int整形一维数组 * @return int整型 */ ///二分法， int find(int[] nums,int l,int r){ while(r>l){ int mid=(l r)/2; if(nums[mid]>nums[mid 1]) //mid右边是下坡 r=mid; else{ //mid右边是上坡 l=mid 1; } } return r; } public int findPeakElement (int[] nums) { // write code here int len=nums.length; if(len==1||nums[0]>nums[1]){ return 0; } if(nums[len-1]>nums[len-2]){ return len-1; } int index=find(nums,0,len-1); //二分法 return index; } }