题解 | #寻找峰值#
寻找峰值
https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76
思路
该题并没有要求将全部的波峰找出,可以使用二分查找找到其中一个波峰即可 设置三个指针mid left right mid向左右比较,指向右边最大者时,更新左指针,反之则相反 直到左指针大于或者等于右指针时,就表明已经找到峰值结束循环返回。 不过有个毛病我很烦,就是当峰值处于边界时不太好判断,所以干脆直接硬编码了。如果有更好的优化思路,欢迎各位大佬提出来
代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int findPeakElement (int[] nums) {
// 代码健壮性检验
if (nums == null) {
return -1;
}
if (nums.length == 1) {
return 0;
}
if (nums.length == 2) {
return nums[0] > nums[1] ? 0 : 1;
}
// 定义三个指针
int left = 0;
int right = nums.length - 1;
int mid = 0;
// 对数组进行二分查找
// 当左指针大于或者等于右指针时,就表明已经找到峰值了
while (left < right) {
// 计算中点的值
mid = (left + right) / 2;
// 校验边界峰值
if (mid == 0) {
return mid;
}
if (left == mid) {
return right;
}
// 先让中点値处左右值互相比较
if (nums[mid - 1] > nums[mid + 1]) {
// 左值更大
if (nums[mid] > nums[mid - 1]) {
// 如果中点値最大,则已经找到一个峰值,直接返回
return mid;
} else {
// 反之,移动右指针到中点位置
right = mid;
}
} else {
// 相同或者右值更大
if (nums[mid] > nums[mid + 1]) {
// 如果中点値最大,则已经找到一个峰值,直接返回
return mid;
} else {
// 反之,移动左指针到中点位置
left = mid;
}
}
}
return mid;
}
}