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.
題意：尋找一個給定數(shù)組的峰值葱绒，峰值有可能存在于波峰上感帅，也可能這個數(shù)組是遞增或遞減的，峰值存在于起始或結(jié)束地淀。
思路：
用二分法查找middle失球，如果middle值比兩邊的值都大，那么middle就是peak帮毁；如果middle處于上坡实苞，那么舍棄middle左側(cè)；如果middle處于下坡或波底烈疚，都可以舍棄右側(cè)黔牵。
如果跳出循環(huán)扔沒有找到peak，那么此時left和right時臨接的爷肝，返回left和right中的較大值就是指定區(qū)間的peak猾浦。
bug:
第一遍做的時候，以為給定數(shù)組肯定會存在一個波峰灯抛，忽略了只有升序或降序的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;
}