牛客网高频算法题系列-BM19-寻找峰值
题目描述
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
- 峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
- 假设 nums[-1] = nums[n] = -\infty−∞
- 对于所有有效的 i 都有 nums[i] != nums[i + 1]
- 你可以使用O(logN)的时间复杂度实现此问题吗？
原题目见：寻找峰值
解法一：数组遍历
首先，判断几种特殊场景：
- 如果数组为空，则不存在峰值；
- 如果数组只有一个元素，因为都是负无穷，所以第一个元素即为峰值；
- 如果数组的第一个元素比第二个元素大，加上左边负无穷，则第一个元素必为峰值；
- 如果数组的最后一个元素比倒数二个元素大，加上右边边负无穷，则倒数第一个元素必为峰值。
如果不存在以上特殊情况，则从数组的第二位开始遍历数组，判断是否是峰值。
解法一：二分法
原理：因为左右都是负无穷，对于中间的元素，如果nums[mid] > nums[mid + 1]，也就是mid部分递减，加上左边负无穷，所以mid的左边一定会有峰值；同理，如果nums[mid] < nums[mid + 1]，加上右边负无穷，所以mid的右边一定会有峰值。
代码
public class Bm019 {
/**
* 遍历数组
*
* @param nums
* @return
*/
public static int findPeakElement(int[] nums) {
// 如果数组为空，则不存在峰值
if (nums == null) {
return -1;
}
// 如果数组的长度为1，则首位即为峰值
if (nums.length == 1) {
return 0;
}
// 如果第一位比第二位大，则第一位必为峰值
if (nums[0] > nums[1]) {
return 0;
}
// 如果最后一位比倒数第二位大，则最后一位必为峰值
if (nums[nums.length - 1] > nums[nums.length - 2]) {
return nums.length - 1;
}
// 如果前面的几种特殊场景不存在，则遍历数组中的元素，逐一判断是否是峰值
for (int i = 1; i < nums.length - 1; i++) {
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
return i;
}
}
return -1;
}
/**
* 二分法
* 原理：因为左右都是负无穷，对于中间的元素，如果nums[mid] > nums[mid + 1]，就是mid部分递减，加上左边负无穷，
* 所以mid的左边一定会有峰值；同理，如果nums[mid] < nums[mid + 1]，加上右边负无穷，所以mid的右边一定会有峰值。
*
* @param nums
* @return
*/
public static int findPeakElement2(int[] nums) {
// 如果数组为空，则不存在峰值
if (nums == null) {
return -1;
}
// 如果数组的长度为1，则首位即为峰值
if (nums.length == 1) {
return 0;
}
// 如果第一位比第二位大，则第一位必为峰值
if (nums[0] > nums[1]) {
return 0;
}
// 如果最后一位比倒数第二位大，则最后一位必为峰值
if (nums[nums.length - 1] > nums[nums.length - 2]) {
return nums.length - 1;
}
int left = 1, right = nums.length - 2;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {2, 4, 1, 2, 7, 8, 4};
System.out.println(findPeakElement(nums));
System.out.println(findPeakElement2(nums));
}
}
相信坚持的力量！
