寻找峰值
难度:
标签:
题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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-231 <= nums[i] <= 231 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
代码结果
运行时间: 16 ms, 内存: 16.0 MB
/*
* 思路：
* 使用二分查找算法来解决问题，但是因为二分查找的过程不适合用 Java Stream 实现，
* 所以我们直接使用标准的二分查找方法。
*/
public class Solution {
public int findPeakElement(int[] nums) {
return binarySearch(nums, 0, nums.length - 1);
}
private int binarySearch(int[] nums, int left, int right) {
if (left == right) {
return left;
}
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
return binarySearch(nums, left, mid);
} else {
return binarySearch(nums, mid + 1, right);
}
}
}解释
方法:
这个题解使用二分查找的方法来寻找峰值。由于题目要求时间复杂度为O(log n)，普通的线性扫描不符合要求。我们可以利用二分查找的思想，每次取中点，比较中点与其右侧相邻元素的大小关系，如果中点较大，说明左侧一定存在峰值，可以缩小范围到左半部分；如果中点较小，说明峰值一定在右半部分，可以缩小范围到右半部分。不断迭代直到左右边界相遇，此时找到了一个峰值。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在二分查找的每次比较中，只比较中点与其右侧相邻元素，而不是同时比较左侧元素？
▷🦆
在二分查找过程中，如果中点和右侧元素相等，该如何处理？题目中提到nums[i] != nums[i+1]，这种情况会出现吗？
▷🦆
题解中提到如果中点大于其右侧元素，峰值一定在左半部分。能否详细解释为什么这样判断峰值的位置是正确的？
▷🦆
在最坏情况下，二分查找需要多少次迭代才能找到峰值？这是否总是等于log_2(n)？
▷相关问题
山脉数组的峰顶索引
符合下列属性的数组
arr 称为 山脉数组 ：
arr.length >= 3- 存在
i（0 < i < arr.length - 1）使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
示例 1：
输入：arr = [0,1,0] 输出：1
示例 2：
输入：arr = [0,2,1,0] 输出：1
示例 3：
输入：arr = [0,10,5,2] 输出：1
提示：
3 <= arr.length <= 1050 <= arr[i] <= 106- 题目数据保证
arr是一个山脉数组