LeetCode 1095. 山脉数组中查找目标值

约 6 分钟
文章信息 10 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 腾讯 字节 微软 美团 百度
标签
数组 二分查找 交互

题目描述

✅ 1095. 山脉数组中查找目标值

image-20260928214628118

image-20260928214628120

题意分析

山脉数组先严格递增，再严格递减，峰顶位于两个端点之间。目标可能在两侧各出现一次，要返回较小的下标，不存在时返回 -1。

数组只能通过 length() 和 get(index) 访问，且 get 最多调用 100 次。长度最多为 $10^4$，逐项读取无法保证满足限制；先找到峰顶，再对两个单调区间分别二分。

解法：找峰顶 + 两次有序二分

核心思路

[!blue]

找峰时让 [left, right] 始终包含峰顶，比较 get(mid) 与 get(mid + 1)。若前者较小，mid 仍在上坡，峰顶一定在它右边，令 left = mid + 1；否则从 mid 开始已经下降，mid 可能就是峰顶，令 right = mid。

每次都保留峰顶并缩小区间，直到 left == right，剩下的位置就是峰顶。循环条件 left < right 配合向下取整的中点，保证 mid < right，因此读取 mid + 1 不会越界。

[0, peak] 严格递增，先在这里搜索，命中就能返回：这一段内没有重复值，且任何下标都小于右段。左段未找到时，再搜索严格递减的 [peak + 1, n - 1]。

目标搜索使用闭区间。升序时，中间值小于目标就去右半边；降序时，中间值大于目标才去右半边。已检查的中点不等于目标，因此更新为 mid + 1 或 mid - 1，区间为空即表示不存在。

解题步骤

  1. 调用一次 length() 记录长度，在 [0, n - 1] 中按相邻元素的坡向二分，得到 peak。
  2. 调用目标搜索函数，在 [0, peak] 上设置 asc = true，按升序比较缩小区间。
  3. 左段命中立即返回；否则在 [peak + 1, n - 1] 上设置 asc = false，按降序比较缩小区间。
  4. 右段仍未命中则返回 -1。峰顶已经包含在左段，不需要另行判断或重复搜索。

代码实现

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        int left = 0;
        int right = n - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            int value = mountainArr.get(mid);
            int nextValue = mountainArr.get(mid + 1);

            if (value < nextValue) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        int peak = left;
        // 先搜索含峰顶的左侧，命中时下标一定小于右侧的任何位置。
        int ans = binarySearch(mountainArr, 0, peak, target, true);

        if (ans != -1) {
            return ans;
        }

        return binarySearch(mountainArr, peak + 1, n - 1, target, false);
    }

    private int binarySearch(
            MountainArray mountainArr, int left, int right, int target, boolean asc) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int value = mountainArr.get(mid);

            if (value == target) {
                return mid;
            }

            // 升序和降序区间的移动方向相反。
            if ((asc && value < target) || (!asc && value > target)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

func findInMountainArray(target int, mountainArr *MountainArray) int {
    n := mountainArr.length()
    left := 0
    right := n - 1
    for left < right {
        mid := left + (right-left)/2
        value := mountainArr.get(mid)
        nextValue := mountainArr.get(mid + 1)
        if value < nextValue {
            left = mid + 1
        } else {
            right = mid
        }
    }

    peak := left
    // 先搜索含峰顶的左侧，命中时下标一定小于右侧的任何位置。
    ans := searchMountain(mountainArr, 0, peak, target, true)
    if ans != -1 {
        return ans
    }
    return searchMountain(mountainArr, peak+1, n-1, target, false)
}

func searchMountain(arr *MountainArray, left int, right int, target int, asc bool) int {
    for left <= right {
        mid := left + (right-left)/2
        value := arr.get(mid)
        if value == target {
            return mid
        }
        // asc 标识当前区间是升序还是降序。
        if (asc && value < target) || (!asc && value > target) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

复杂度分析

  • 时间复杂度：$O(\log n)$。找峰每轮调用两次 get，两次目标搜索每轮各调用一次。当 $n \leq 10^4$ 时，每次二分至多进行 14 轮，总调用量至多为 $2\times14+14+14=56$ 次，满足 100 次的限制，无需额外缓存。
  • 空间复杂度：$O(1)$，只使用常数个下标和临时值。

关键点总结

[!green]

  • 调用次数限制决定必须使用对数算法；不能先把接口内容复制成普通数组。
  • 用相邻元素判断坡向，先定位唯一峰顶，再获得两个单调区间。
  • 左段包含峰顶，右段不含峰顶；先左后右保证最小下标。
  • 同一个二分函数用 asc 表示顺序，降序区间的移动方向与升序相反。

易错点总结

[!yellow]

  • 找峰使用 left <= right 时，mid 可能到达末尾，访问 mid + 1 越界；应使用 left < right。
  • 左段写成 [0, peak - 1] 会漏掉 target 恰为峰值的情况。
  • 降序段沿用升序更新方向，会排除真正答案；降序中值偏大时应向右。
  • 先搜右段可能返回较大下标；必须先搜左段并在命中后立即返回。

相似题目

题目 难度 关联与区别
852. 山脉数组的峰顶索引 中等 先定位峰顶，再分别对升序段与降序段搜索；原题只要求峰顶索引。
704. 二分查找 简单 两侧都可二分，但降序段比较方向相反，若两侧都有目标应优先较小下标。
162. 寻找峰值 中等 通过中点与相邻值的坡向保留必含峰值的一侧；本题先定位山顶再分别搜索两侧，该题寻找任意局部峰值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/33128240
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！