Leetcode 162.寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 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]

思路：寻找峰值，最大值就一定是峰值，但这样遍历是行不通的，复杂度就到了O(n)，所以每次操作必须寻找减小范围的方法，其核心就是找到规律，该题必有峰值，因为边界是无限小，而且一个节点左右节点都是不相同的，一个节点的峰值情况，无非三种情况，左小右小，那么该值就是峰值，左小右大，那么峰值必在右边因为有上升就必然会下降，最坏情况就是到边界下降到无穷小。所以按此规律，可以直接进行范围缩小。代码如下：和基本二分类似。

class Solution {public int findPeakElement(int[] nums) {// 由于数组边界是无穷小，所以一个元素i，如果i大于两侧，那么他就是峰值// 如果右侧大于i，右侧就必有峰值，左侧同理，这种情况就可以使用二分思想int leftIndex = 0;int rightIndex = nums.length - 1;while (true) {int middleIndex = (leftIndex + rightIndex) / 2;if (compare(nums, middleIndex, middleIndex-1) && compare(nums, middleIndex, middleIndex+1)) {return middleIndex;    } else if (nums[middleIndex+1] > nums[middleIndex]) {leftIndex = middleIndex + 1;} else {rightIndex = middleIndex - 1;}}}// 由于数据中可能会有int的最小值，所以必须写比较函数public boolean compare(int[] nums, int index1, int index2) {if (index1 < 0 || index1 >= nums.length) {return false;}if (index2 < 0 || index2 >= nums.length) {return true;}return getNum(index1, nums) > getNum(index2, nums);}public int getNum(int index, int[] nums) {return nums[index];}
}