本文主要是介绍[M二分] lc162. 寻找峰值(二分+思维+好题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 1. 题目来源
- 2. 题目解析
1. 题目来源
链接:162. 寻找峰值
题单:
-
- 二分算法(二分答案/最小化最大值/最大化最小值/第K小)
- 其他
2. 题目解析
本题是而二分法的一个经典变种,也说明了一点:
- 当数组即便无序时,只要其满足二分性质,则也可以进行二分。
思路:
- 首先,本题答案一定存在。因为在两侧边界是属于 -inf,负无穷的高度。
- 那么只要存在一点 x,x-1<x,且 x<x-1 则 x 即为峰值。
- 那么我们直接考虑峰值点,即答案点在那里。
- 取答案所处区间
[l, r]
,中间的点为 mid。 - 判断 nums[mid] > nums[mid + 1],即判断 mid 点是否大于 mid+1 点。
- 且由于答案一定存在,那么答案一定在 [l, mid] 之间也存在。因为,只需要在 mid 的左侧找到一个小于 nums[mid] 的就构成了递减区间,就是答案。即便都找不到,那也有 nums[0] 顶着。
- 取答案所处区间
- 故,每次都去判断一下 nums[mid] > nums[i + 1] 之间的关系。就可以将区间一分为 2,向答案所处位置逼近。最终取到答案。
实现细节
- 二分中,不用取判断 nums[mid+1] 是否会越界,因为当越界时,mid=n-1 才对,此时仅有 l=r=n-1 才能构成此情况。但当 l=r 时,将不会进入 while 循环。所以此种情况是不会出现的。
- 时间复杂度: O ( l o g n ) O(logn) O(logn)
- 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
public:int findPeakElement(vector<int>& nums) {int n = nums.size();int l = 0, r = n - 1;while (l < r) {int mid = l + r >> 1;if (nums[mid] > nums[mid + 1]) r = mid;else l = mid + 1;}return l;}
};
这篇关于[M二分] lc162. 寻找峰值(二分+思维+好题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!