文章目录
寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log 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。
提示：
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element
方法一：
根据观察，如果存在峰值，那么这个峰值就会比他前后两个数字的值都要大，这时候只要拿当前这个元素的值和他前后两个元素的值进行比较，从而可以判断出这个元素是否为峰值。但是有两种情况需要考虑的是，就是连续升序和连续降序的情况，这时候，是没有办法进行比较前后两个元素的，此时只要保证了下标为0的元素比下标为1的元素的值要大，这时候就说明下标为0的元素是一个峰值，因为存在了降序的趋势，同样的，如果下标为nusm.length - 1的元素的值比他前一个元素的值要大，说明存在着升序的趋势，此时，nums.length - 1对应的值就是一个峰值，因为题目中已经明确说明了nums[-1] = nums[nums.length]= -∞,所以这两个端点只要满足了这两个条件，就必然是个峰值。
否则，如果两个端点并没有满足条件，那么这时候说明下标为0的地方存在着升序的情况，而下标为nums.length - 1存在着降序，此时两者的中间必然存在峰值才会出现先升后降的趋势，因此，只要通过nums[i - 1] < nums[ i ] && nums[ i ] > nums[ i + 1]来找到峰值即可。
class Solution {
public int findPeakElement(int[] nums) {
if(nums.length == 1)
return 0;
int i;
for(i = 0; i < nums.length; ++i){
if(i == 0 && nums[i] > nums[i + 1]){
//如果是连续降序或者先降序后升序，那么始终第一个元素是一个峰值，所以可以直接返回下标0
return i;
}else if(i == nums.length - 1 && nums[i] > nums[i - 1]){
//如果连续升序，那么数组的最后一个元素才是峰值
return i;
}else{
//数组并不是连续单调的，那么根据当前元素（不是端点）大于前后两个元素，从而得出当前元素是一个峰值，返回其下标
if(i > 0 && i < nums.length - 1 && nums[i - 1] < nums[i] && nums[i] > nums[i + 1])
return i;
}
}
return -1;
}
}
运行结果：
方法二：二分查找
我们知道，二分查找只应用于一个数组有序的地方，为什么这里也可以应用呢？因为我们可以发现部分数组是有序的，而我们就是要找这部分有序数组的最大值。因此可以应用二分查找。
- 在low <= high的情况下进行二分查找
- 在low等于high的情况，直接返回low，表示当前元素就是一个峰值
- 否则获取中间值mid = low + (high - low) / 2,当然也可以是mid = (high + low) / 2
- 将nums[mid]和nums[mid + 1]进行比较，如果nums[mid]更大，说明[mid,mid + 1]之间存在着降序，此时mid对应的值可能是一个峰值，当然也可能不是,因为可能在[low,mid]可能是升序，也可能是降序的，所以mid对应的值不一定是峰值，此时需要更新high为mid，否则，如果nums[mid]更小，说明[mid,mid + 1]存在升序的趋势，此时mid必然不是峰值，而mid + 1也不一定是峰值，因为[mid + 1,high]可能是升序，也可能是降序，所以我们需要在[mid + 1,high]中寻找，所以更新low = mid + 1.
对应代码：
class Solution {
/*
利用二分查找，首先获得中间值nums[mid]
这时候我们将其和mid + 1的值进行比较，如果mid的值更小，
那么说明存在升序，所以这时候需要更新low = mid + 1
否则，如果mid更大，说明存在降序这时候我们不可以
直接考虑mid的值就是峰值，因为存在着连续降序的可能，所以
不可以返回mid，而应该更新high=mid
当low>high时候，直接返回low即可
*/
public int findPeakElement(int[] nums) {
int low = 0,high = nums.length - 1,mid;
while(low <= high){
if(low == high)//如果存在峰值，那么必然有low = high的情况
return low;
mid = low + (high - low) / 2;
if(nums[mid] > nums[mid + 1]){
//当前mid对应的值大于mid + 1对应的值，此时说明存在降序，此时不可以
//返回mid，因为存在连续降序的情况，所以需要更新high为mid
high = mid;
}else{
//当前的mid的值小于mid + 1的值，说明存在着升序，此时，需要更新low = mid + 1
low = mid + 1;
}
}
return -1;
}
}
运行结果：