题目描述
题目链接
思路
假设数组长度为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;
}
}
更多
算法和数据结构笔记
