高频面试题：找出峰值元素
大家好，我是戴先生 今天给大家介绍一下如何利用玄学二分法找出峰值元素 想直奔主题的可直接看思路3 题目 给定一个整数数组 求出数组中任一峰值元素的索引地址i 注意： 1、峰值元素是指其值严格大于左右相邻值的元素 2、对于所有有效的 i 都有 nums[i] != nums[i + 1] 3、如果存在多个峰值元素，返回任一峰值元素索引即可
题解
根据题目，峰值元素其实就是将数组转换为坐标轴函数之后的极大值
可以简单地归为以下三种情况
第一种情况就是数组是单调递增或递减的
这种情况只存在一个峰值元素，为数值7
第二种情况数组先单调递减（增），再单调递增（减）
这种情况存在两（一）个峰值元素
为数值7，7（5）
第三种情况数组存在多个单调递增和递减的区间
这种情况存在多个峰值元素
为数值4，7，4
思路1
高中数学告诉我们：最大值一定是极大值
所以很简单了
只要求出数组中的最大值就可以了
求出最大值的方法就多了
最简单的就是遍历所有元素
代码实现1
思路1的代码实现如下
public static int findPeekElement1(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int result = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[result]) {
result = i;
}
}
return result;
}思路2
在思路1的基础上我们可以做一下优化
题目要求我们找出任一极大值即可
所以我们在遍历数组的时候
只要找到了符合条件（大于左边和右边的值）的数
就能直接返回结果了
唯一需要注意的是首、尾两个值的情况
因为这两个值是没有“左边”或“右边”的值
所以如果在除了首尾之外的元素中没有找到符合条件的值
只需要比较一下首尾两个值，较大者即为极大值，且是最大值
代码实现2
思路2的代码实现如下
public static int findPeekElement1(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
for (int i = 1; i < nums.length - 1; i++) {
if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
return i;
}
}
return nums[0] >= nums[nums.length - 1] ? 0 : nums.length - 1;
}思路3
思路1和思路2的时间负责都都是O(n)
那么有没有办法将时间复杂度优化一下呢？
给大家说一个思路
凡是遇到有序数据或有规律的区间有序数组
第一个可以尝试的方法就是玄学算法：二分法
如图所示
通过二分法找到第一个中间值mid的时候
如果nums[mid -1] < nums[mid]
那么mid或mid的右侧一定存在一个极大值
那么就可以将范围锁定到mid~end之间
同理
如果如果nums[mid -1] > nums[mid]
那么在mid或者mid的左侧必然存在一个极大值
那么就可以将范围锁定到start~mid之间
思路明确之后代码就很好实现了
而且二分算法的时间复杂度为log(n)
代码实现3
思路3的代码实现如下
public static int findPeekElement2(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
int mid;
while (start + 1 < end) {
mid = (start + end) / 2;
if (nums[mid - 1] > nums[mid]) {
end = mid;
} else if (nums[mid + 1] > nums[mid]) {
start = mid;
} else {
return mid;
}
}
return nums[start] > nums[end] ? start : end;
}测试验证
以上分别是三个方法的时间和空间消耗对比
明显二分法再次胜出
文/戴先生@2022年05月15日
---end---
腾讯云开发者
