LeetCode LCR 069. 山脉数组的峰顶索引

2026-03-28 HGNULB 约 7 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 简单 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 069. 山脉数组的峰顶索引

题意分析

给一个「山脉数组」——存在某个下标 i，使得数组在 [0, i] 上严格递增、在 [i, n-1] 上严格递减——要求返回峰顶下标 i。

题目保证输入一定是山脉数组，这是一个很强的前提：峰顶必然存在且唯一，不需要考虑平台、多峰或单调数组。同时它保证 i 一定满足 $0 < i < n - 1$，也就是峰顶不可能在两端，两侧至少各有一个元素。

「严格」递增与递减意味着不存在相邻相等的元素，因此相邻两项的大小关系永远能明确指出方向，不会出现无法判断的情况。这是二分能成立的关键。

约束里 $n$ 可达 $10^5$ 且题目要求 $O(\log n)$，线性扫描虽然能过但不是要的答案。

边界上要注意：数组最短是 3，此时峰顶只能是下标 1；峰顶两侧的长度可以极不对称，不能假设峰顶在中间附近。

解法：二分查找判定答案

核心思路

暴力做法是从左往右扫，找到第一个满足 arr[i] > arr[i+1] 的下标返回。$O(n)$，正确但没利用山脉的结构。

瓶颈在于线性扫描把每个位置都当成独立候选逐个验证，而山脉形状其实提供了强得多的信息：只要看某个位置和它右邻居的大小关系，就能判断峰顶在它的哪一侧，一次比较就能砍掉一半区间。

观察相邻关系 arr[mid] 与 arr[mid + 1]：若 arr[mid] > arr[mid + 1]，说明 mid 已经落在下降段（或正好是峰顶），峰顶必定在 mid 或其左侧；若 arr[mid] < arr[mid + 1]，说明 mid 还在上升段，峰顶必定严格在 mid 右侧。因为严格单调，两种情况必居其一，没有第三种可能。

于是问题变成在下标区间上找边界：把「arr[i] > arr[i+1]」看成一个从假变真且只变一次的布尔序列——上升段全部为假、峰顶及之后全部为真——要找的正是第一个为真的位置，它就是峰顶。

搜索区间取 [1, n - 2]。左端从 1 开始是因为题目保证峰顶不在下标 0；右端到 n - 2 有两重理由：峰顶不可能是最后一个元素，而且判定式里要访问 arr[mid + 1]，mid 最大只能取到 n - 2 才不越界。

维持的不变量是：峰顶始终落在 [left, right] 内；left 左侧的位置全部处于上升段，right 右侧的位置全部处于下降段。每轮判定后，满足条件的 mid 保留（right = mid），不满足的排除（left = mid + 1），区间严格缩短，最终收敛到唯一的峰顶。

解题步骤

令 left = 1、right = arr.length - 2。这个区间就是峰顶的全部可能取值范围，由题目「峰顶不在两端」的保证直接得出；同时也保证判定式访问 arr[mid + 1] 时下标合法。

循环条件写 left < right，区间收缩到只剩一个候选时退出。

每轮取中点 mid = (left + right) >> 1，用 arr[mid] 与 arr[mid + 1] 比较。比较的是相邻两项而不是 arr[mid] 与某个固定值，因为数组无序，绝对值大小提供不了方向信息，只有局部趋势可以。

若 arr[mid] > arr[mid + 1]，说明从 mid 到 mid+1 已经在下降，峰顶不可能在 mid 右边，令 right = mid。保留 mid 是因为它自己可能就是峰顶。

否则 arr[mid] < arr[mid + 1]，仍在上升，峰顶必在 mid 右侧，令 left = mid + 1 把 mid 排除。排除是安全的：上升段上的点绝不可能是峰顶。

退出循环时 left == right，返回 left 即为峰顶下标。不必再验证一次，不变量已经保证了正确性。

以 arr = [0, 2, 4, 3, 1] 走一遍：初始 left = 1、right = 3。第一轮 mid = 2，比较 arr[2] = 4 与 arr[3] = 3，前者更大说明已在下降段，峰顶在 mid 及左侧，right = 2，区间变成 [1, 2]。第二轮 mid = 1，比较 arr[1] = 2 与 arr[2] = 4，前者更小说明还在上升，峰顶严格在右，left = 2，区间变成 [2, 2]。此时 left == right，退出并返回 2——arr[2] = 4 确实是峰顶。整个过程只做了两次比较，从未访问 arr[0] 和 arr[4]。

代码实现

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 1, right = arr.length - 2;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > arr[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

func peakIndexInMountainArray(arr []int) int {
    left, right := 1, len(arr)-2
    for left < right {
        mid := (left + right) >> 1
        if arr[mid] > arr[mid+1] {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

复杂度分析

时间复杂度：$O(\log n)$，每轮比较后候选区间至少减半，从长度 $n - 2$ 收敛到 1 只需 $\lceil \log_2 n \rceil$ 轮。

空间复杂度：$O(1)$，只使用了 left、right、mid 三个下标变量，与数组规模无关。

关键点总结

数组无序时二分依然可用，前提是能从局部信息推断答案在哪一侧。本题靠的是相邻两项的趋势，而不是元素与目标值的大小关系——这是二分适用范围的重要拓展。

把「arr[i] > arr[i+1]」看成一个只从假变真一次的布尔序列，问题立刻规约成标准的「找第一个为真」左边界二分，可以直接复用同一套收缩规则。

搜索区间的两端应当由答案的取值范围和判定式的访问范围共同决定。本题两个约束恰好都指向 [1, n-2]，少考虑任何一条都可能越界或漏解。

满足条件的 mid 保留、不满足的排除，是左边界二分不丢解且不死循环的根本规则；写任何二分前先想清楚「mid 有没有资格当答案」。

「严格单调」的保证消除了相邻相等的情形，判定才能二选一。若题目允许相等（存在平台），这套二分立刻失效，只能退回线性扫描或额外处理。

面试视角：先说清楚「峰顶等价于第一个满足 arr[i] > arr[i+1] 的位置」，再套二分模板，比直接写循环更有说服力；面试官通常就是想听这句等价转化。

面试视角：常见追问是 162 题——数组不再保证山脉形状、可能有多个峰值。此时同一套代码依然正确，因为把两端视为负无穷后「向上爬」的方向总能指向某个峰值，可以主动提出来证明你理解的是不变量而非特例。

易错点总结

错误写法：区间取 left = 0、right = arr.length - 1。用例 arr = [0, 2, 1] → mid 可能取到 n - 1，判定式访问 arr[n] 直接下标越界。

错误写法：满足 arr[mid] > arr[mid+1] 时写 right = mid - 1。用例 arr = [0, 2, 1] → 峰顶下标 1 恰好在某轮成为 mid，被直接排除，最终返回 0 或抛出区间非法。

错误写法：不满足时写 left = mid。用例 arr = [0, 1, 0] 之类的两候选区间 → mid 恒等于 left，区间不再收缩，死循环。

错误写法：把判定改成 arr[mid] > arr[mid - 1] 并据此向右收缩。用例 arr = [0, 2, 4, 3, 1] → 上升段与峰顶都满足这个条件，布尔序列不再是「只翻转一次」的形态，二分收敛到的位置不是峰顶。

错误写法：判定写成 arr[mid] >= arr[mid + 1]。用例严格山脉下结果相同，但一旦数据出现平台（如 [0, 2, 2, 1]）→ 平台整段被判为下降，返回平台左端而非真正的峰顶；等号的取舍必须与「严格」这一前提对应。

错误写法：循环条件写 left <= right 且循环内仍用 right = mid。用例 arr = [0, 2, 1] → left 与 right 相等后仍进入循环且 right 不再变化，死循环。

错误写法：试图用「找最大值」的思路做二分，比较 arr[mid] 与 arr[left] 或 arr[right] 的大小。用例 arr = [0, 10, 5, 4, 3, 2, 1] → arr[mid] 与端点的关系无法区分「在上升段」还是「在下降段的高处」，收缩方向判断错误。

错误写法：返回 arr[left] 而不是 left。用例 arr = [0, 2, 1] → 返回峰顶的值 2 而不是下标 1，题目要的是索引。

相似题目

题目	难度	考察点
852. 山脉数组的峰顶索引	中等	与本题同题，可用来对照线性扫描与相邻趋势二分的差距
162. 寻找峰值	中等	不保证山脉形状且峰值可能有多个，需论证「向上爬必遇峰」的正确性
1095. 山脉数组中查找目标值	困难	在本题基础上还要在两个单调段各做一次二分，且访问次数受限
704. 二分查找	简单	判定依据回到元素与目标的比较，是最基础的有序二分
35. 搜索插入位置	简单	同为左边界二分，区间右端需扩到 $n$ 以容纳插入末尾的答案
540. 有序数组中的单一元素	中等	判定依据是下标配对的奇偶性，同样属于「非比较值」的二分
153. 寻找旋转排序数组中的最小值	中等	靠与端点比较判断落在哪一段，收缩规则的论证方式与本题互补