【leetcode】寻找峰值 [m](二分)-爱代码爱编程
一、题目
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1:
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
提示:
- 1 <= nums.length <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- 对于所有有效的 i 都有 nums[i] != nums[i + 1]
二、代码
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
// 数组长度为1,直接返回0下标
if (n == 1) {
return 0;
}
// 先判断两个特殊情况,也就是数组两头的数是不是局部最小,如果是的话直接返回。反正题目只要求返回一个符合局部最小的数即可
if (nums[0] > nums[1]) {
return 0;
}
if (nums[n - 1] > nums[n - 2]) {
return n - 1;
}
// 执行到这里,左右两端的数一定都小于相邻的数
// 设置数组的左右范围
int l = 0;
int r = n - 1;
// L...R 肯定有局部最大。
// 最左端的数比相邻的数小,最右端的数比相邻的数小,因为相邻的数没有相等的,他们在坐标系上的线是一个向下凹的弧度,所在在中间必然有一个值既大于左边相邻的数,也大于右边相邻的数。
// 开始通过二分法进行查找
while (l < r - 1) { // 这里用的是L < R - 1,之所以用R - 1是因为怕越界,因为要想判断mid,mid-1,mid+1就要保证这三个位置都在L~R的范围里面,所以这里就要让L < R - 1。
// 设置中间下标
int mid = (l + r) >> 1;
// 如果找到了符合局部最大的数,直接返回其下标
if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
return mid;
} else {
// 如果中间位置的数小于其左侧相邻的数,说明mid-1的数至少是大于mid的,所以保留mid-1,去左半段继续查找,更新R的值即可
// 我们要找凸线的最高点,此时mid-1位置比mid的更高,自然要去左侧找凸线的最高点
if (nums[mid] < nums[mid - 1]) {
r = mid - 1;
// 反之,说明mid+1的数是大于等于mid的,所以保留mid+1,去右半段继续查找,更新L的值即可
} else {
l = mid + 1;
}
}
}
// 如果跳出循环还没有找到局部最大,说明当前L~R范围的数只有2个或者1个,这样我们就直接判断这两个数谁比较大就返回谁。因为L位置一定比左侧的数大,R位置一定比右侧的大,只要是比较出L和R谁大,就能知道谁是局部最大了
// 如何L = R,说明范围内只有一个数,直接将其返回即可
return nums[l] > nums[r] ? l : r;
}
}
三、解题思路
先去判断数组两端的两个数是不是满足局部最大,如果满足了直接返回下标即可。如果不满足,再去进行后续的流程。
进行后面的流程,一定能保证左右两端的数都比其相邻的数小,所以左右两端的斜率都是向上的,然后整个坐标系连线一定是连在一起的,那就说明一定会在坐标系的中间某个位置再连在一起,一开始左右两端斜率都向上,所以中间必然存在一个位置斜率为0,让左右的线连接在一起,而这个位置也就比左右都小。所以在坐标系看就是一个凸形的线。所以中间必然有一点即比左边的数大,又比右边的数大。
任意两个都相邻是不相等的,所以中间必然存在一个变化曲线,先往上扬,后是下降,中间我不管你怎么连这个变化曲线一定存在局部最大。