一、题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 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]
二、解题思路
- 初始化左指针left为0，右指针right为nums.length - 1。
- 在二分查找的过程中，比较中间位置mid的元素与mid+1位置的元素： a. 如果nums[mid] > nums[mid + 1]，说明峰值在mid左边（包含mid位置），将right赋值为mid。 b. 如果nums[mid] < nums[mid + 1]，说明峰值在mid右边（不包含mid位置），将left赋值为mid+1。
- 重复步骤2，直到left >= right。
- 返回left位置的元素即为峰值。
三、具体代码
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 二分查找算法的时间复杂度通常是 O(log n)，其中 n 是数组或搜索空间的长度。
- 在这个问题中，我们使用二分查找来缩小可能的峰值位置的范围。
- 在每次迭代中，我们将搜索空间减半，因此迭代次数是 log n。
- 因此，这个算法的时间复杂度是 O(log n)。
2. 空间复杂度
- 空间复杂度主要取决于算法使用的额外空间。
- 在这个问题中，我们只使用了几个额外的变量（left, right, mid），不管输入数组的大小如何，这些变量的空间占用是常数级别的。
- 因此，这个算法的空间复杂度是 O(1)，即常数空间复杂度。
综上所述，该代码的时间复杂度是 O(log n)，空间复杂度是 O(1)。
五、总结知识点
二分查找算法：这是一种高效的查找算法，它通过不断将搜索区间减半来快速定位目标值的位置。二分查找适用于有序数组或者具有特定性质的数组。
循环条件：
while (left < right)是二分查找的标准循环条件，用于控制查找过程，直到找到目标值或者搜索区间为空。中间位置的计算：
int mid = left + (right - left) / 2;是计算中间位置的常见方式，它避免了直接使用(left + right) / 2可能导致的整数溢出问题。比较和区间调整：
if (nums[mid] > nums[mid + 1])用于比较中间位置的元素与其右侧邻居的大小关系，从而决定峰值可能存在的区间。如果中间元素大于其右侧邻居，说明峰值在左侧，否则在右侧。指针的更新：
right = mid;和left = mid + 1;分别用于更新搜索区间的左右边界。这取决于比较的结果，如果中间元素大，则保留左侧区间；如果中间元素小，则保留右侧区间。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
