leetcode
leetcode 3001 ~ 3050
山脉数组的峰顶索引

山脉数组的峰顶索引

难度:

标签:

题目描述

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]`?这样做是否有可能跳过峰顶?
如果中点元素小于其右侧元素,表明中点到中点右侧元素之间是递增的,因此峰顶必定在中点的右侧。更新`left`为`mid + 1`是为了排除中点元素,因为已知它不是峰顶。这种更新方式不会跳过峰顶,因为按照山脉数组的特性,峰顶一定在递增序列的右侧。
🦆
如何处理边界情况,如数组中所有元素均为递增或递减时?这种情况下二分查找是否仍然有效?
如果数组全部递增或递减,则不符合山脉数组的定义。山脉数组要求数组中存在一个峰顶,即元素先递增后递减。在完全递增或递减的数组中应用本算法可能导致不正确的结果或无法找到峰顶。在实际应用中,应首先验证数组是否符合山脉数组的定义。如果确认是山脉数组,二分查找方法才是有效的。

相关问题