根据mid位置的数字与mid+1位置数字的大小将区间分为两种情况:
1.nums[mid]<nums[mid+1]
此时,若右边一旦出现下降趋势,则下降趋势前的点就是峰值。若没有下降趋势,右端点就是峰值。
即峰值一定在[mid+1, r]区间内。
2.nums[mid]>nums[mid+1]
此时,若左边一旦出现下降趋势,则下降趋势前的点就是峰值。若没有下降趋势,左端点就是峰值。
即峰值一定在[l, mid]区间内。
具有二段性,可通过二分来解决。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
// 这里mid+1一定不会越界,因为l<r时,mid向下取整永远不会取到r
if (nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return r;
}
};