A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1]
, find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞
.
For example, in array [1, 2, 3, 1]
, 3 is a peak element and your function should return the index number 2.
click to show spoilers.
题意：寻找一个给定数组的峰值，峰值有可能存在于波峰上，也可能这个数组是递增或递减的，峰值存在于起始或结束。
思路：
用二分法查找middle，如果middle值比两边的值都大，那么middle就是peak；如果middle处于上坡，那么舍弃middle左侧；如果middle处于下坡或波底，都可以舍弃右侧。
如果跳出循环扔没有找到peak，那么此时left和right时临接的，返回left和right中的较大值就是指定区间的peak。
bug:
第一遍做的时候，以为给定数组肯定会存在一个波峰，忽略了只有升序或降序的case
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int peak = -1;
int left = 0, right = nums.length - 1;
while (left + 1 < right) {
int middle = left + (right - left) / 2;
if (nums[middle] > nums[middle - 1] && nums[middle] > nums[middle + 1]) {
return middle;
} else if (nums[middle] > nums[middle - 1] && nums[middle] < nums[middle + 1]) {
left = middle;
} else {
right = middle;
}
}
return nums[left] > nums[right] ? left : right;
}