题目描述
思路
假设数组长度为N，首先判断0号位置的数和N-1位置的数是不是峰值位置。
0号位置只需要和1号位置比较，如果0号位置大，0号位置就是峰值位置。
N-1号位置只需要和N-2号位置比较，如果N-1号位置大，N-1号位置就是峰值位置。
如果0号位置和N-1在上轮比较中均是最小值，那么数组的样子必然是如下情况：
从0..1是增长
从N-2...N-1是下降
那么峰值位置必在1...N-2之间出现
此时可以通过二分来找峰值位置，先来到中点位置，假设为mid，如果:
arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]
mid位置即峰值位置
否则：
如果趋势是：
则在 1...(mid-1)区间内继续上述二分
如果趋势是：
则在 (mid+1)...(N-2)区间内继续上述二分。
完整代码
public class LeetCode_0162_FindPeakElement {
public int findPeakElement(int[] nums) {
int n = nums.length;
if (n == 1) {
return 0;
}
if (n == 2) {
return nums[0] == Math.max(nums[0], nums[1]) ? 0 : 1;
}
if (nums[n - 1] > nums[n - 2]) {
return n - 1;
}
if (nums[0] > nums[1]) {
return 0;
}
int L = 1;
int R = n - 2;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
return mid;
} else if (nums[mid] < nums[mid + 1]) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return -1;
}
}