山脉数组的峰顶索引
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 16 ms, 内存: 16.9 MB
/*
* 思路:
* 使用Java Stream API实现峰值索引查找。
* 由于Stream API的限制,无法直接实现二分查找,但可以通过IntStream来遍历数组并找到峰值索引。
* 该实现时间复杂度为O(n),不如二分查找的O(log(n))高效。
*/
import java.util.stream.IntStream;
public class Solution {
public int peakIndexInMountainArray(int[] arr) {
return IntStream.range(1, arr.length - 1)
.filter(i -> arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
.findFirst()
.orElse(-1);
}
}
解释
方法:
该题解采用二分查找方法寻找山脉数组的峰顶索引。在山脉数组中,由于数组的元素先递增后递减,因此可以通过比较中间元素与其右侧元素的关系来确定峰顶的位置。如果中间元素大于其右侧元素,则峰顶在左侧,包括当前中间位置;如果中间元素小于其右侧元素,则峰顶在右侧。通过不断调整左右边界,缩小查找范围,最终找到峰顶。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在二分查找法中,当发现中点元素大于其右侧元素时,可以确定峰顶在左侧或是中点?
▷🦆
在实现中,为什么选择将`left`更新为`mid + 1`而非`mid`当`arr[mid] < arr[mid + 1]`?这样做是否有可能跳过峰顶?
▷🦆
如何处理边界情况,如数组中所有元素均为递增或递减时?这种情况下二分查找是否仍然有效?
▷