问题描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums
,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞
。
你必须实现时间复杂度为 O(log n)
的算法来解决此问题。
提示:
- 1 <= nums.length <= 1000`
- -231 <= nums[i] <= 231 - 1`
- 对于所有有效的
i
都有nums[i] != nums[i + 1]
示例
示例 1:
输入:nums = [1,2,3,1]
输出:2
解释:3 是峰值元素,你的函数应该返回其索引 2。
示例 2:
输入:nums = [1,2,1,3,5,6,4]
输出:1 或 5
解释:你的函数可以返回索引 1,其峰值元素为 2;
或者返回索引 5, 其峰值元素为 6。
解题思路
这题按常规的思路来解答并不难,只需遍历一次数组即可,关键是要达到题目中要求的O(log n)
的时间复杂度。这个时间复杂度的搜素算法最先想到的是二分查找,然而,二分查找一般是用于查找有序数组,而 nums
题目中并没有说明是有序的。
二分查找的本质是不断将搜索空间划分为两个部分,并每次都舍弃其中一部分,只在另一部分进行下次搜索。那么,要使用二分查找就必须保证我们要的解一定在保留的部分中。假设,我们将nums 划分为 [low, mid] 和 [mid + 1, high] 两个部分如果 mid 不是解,那么有没有可能其中一个区间一定存在解呢?
很简单,由于相邻元素不可能相等,我们只需要令 nums[low - 1] < nums[low]
以及 nums[mid] > nums[mid + 1]
即可保证 [low, mid]
区间中一定有解。或者令 nums[mid + 1] > nums[mid]
以及 nums[high] > nums[high + 1]
也能保证 [mid + 1, high]
中有解。证明如下:
假设 nums[low - 1] < nums[low]
且 nums[mid] > nums[mid + 1]
时, [low, mid]
中无解,则:
nums[low] < nums[low + 1] < nums[low + 2] < ... < nums[mid - 1]
成立- 如果此时
nums[mid - 1] < nums[mid]
,则nums[mid]
为峰值 - 如果此时
nums[mid - 1] > nums[mid]
, 则nums[mid - 1]
为峰值
因此,无法满足 nums[low - 1] < nums[low]
且 nums[mid] > nums[mid + 1]
成立时,[low, mid]
无解的假设。同理可以证明其它假设。
既然如此,我们只需令更新后的 low 和 high 满足 nums[low - 1] < nums[low]
以及 nums[high] > nums[high + 1]
即可。代码如下:
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int low = 0;
int high = nums.size();
int mid;
if(nums.size() == 1){ // 判断nums长度为1的情况
return 0;
}
if(nums[0] > nums[1]){ // 判断nums[0] 为峰值的情况
return 0;
}
if(nums[nums.size() - 1] > nums[nums.size() - 2]){ // 判断nums[n-1]为峰值的情况
return nums.size() - 1;
}
while(low < high){ // 此时,nums.length > 2,否则之前就已经找出峰值点了
mid = (low + high) / 2;
if(nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]){ // 判断mid是否是峰值点
return mid;
}
else if(nums[mid] < nums[mid - 1]){ // 更新high
high = mid;
}
else{ // 更新low
low = mid + 1;
}
}
return mid;
}
};
标签:high,return,nums,mid,峰值,力扣,low,leetcode,162
From: https://www.cnblogs.com/greatestchen/p/16939679.html