山脉数组的峰顶索引 图解题解

山脉数组的峰顶，题目让你返回什么

给一个山脉数组 arr：它先严格递增爬到某个最高点，再严格递减下来，像一座只有一个尖的山。题目保证有且只有一个峰，要你返回峰顶元素的下标（不是峰顶的值）。题面 arr=[0,3,6,9,12,15,18,21,17,13,9,5,1]，21 排在第 7 格，所以返回 7。

一格格扫过去找拐点，慢在哪

从左往右一格格扫，找第一个 arr[i] 大于 arr[i+1] 的位置，那个 i 就是峰顶。可这要把整座山从山脚走到山顶，数组有 n 个数，峰若靠右就得比满将近 n 次，时间 O(n)。题目给的严格单峰、两侧都单调（左边只升、右边只降）的结构，被一格格扫白白浪费了。

单峰撑腰，比一下邻居就知道往哪走

靠的就是『先升后降、只有一个峰』这个保证。站在任意一格 mid，拿它和右邻居 arr[mid+1] 比：arr[mid] 小于右邻说明还在往上爬，峰顶必在它右边，左半连 mid 一起扔；arr[mid] 大于右邻说明已在下坡，峰顶在 mid 左边或就是它。一次比较就砍掉一半，正因为单峰，被丢的那半绝不藏更高的点。

上坡推左界、下坡收右界，循环为什么写 l 小于 r

用两个下标 l、r 圈住还没排除的范围，起初 l=0、r=n-1。每轮取中点 mid=(l+r)//2，和右邻 arr[mid+1] 比：上坡（arr[mid] 小于 arr[mid+1]）就让 l 跳到 mid+1，丢掉含 mid 的左半；下坡就让 r 收到 mid——是 mid 本身、不是 mid-1，因为 mid 自己可能就是峰顶，减一会把它一起丢。

循环条件写 while l 小于 r，收到 l==r 就停，范围只剩一格、它就是峰顶。这里有条不变量（每轮都成立的保证）：峰顶始终落在 [l,r] 内，每轮要么 l 前进、要么 r 后退，只缩不漏。

[0,3,6,…,21,…,1] 逼到第 7 格

起点 l=0、r=12。第一轮 mid=(0+12)//2=6，arr[6]=18 小于 arr[7]=21 是上坡，l 跳到 7。第二轮 l=7、r=12，mid=9，arr[9]=13 大于 arr[10]=9 是下坡，r 收到 9。第三轮 l=7、r=9，mid=8，arr[8]=17 大于 arr[9]=13 还是下坡，r 收到 8。第四轮 l=7、r=8，mid=7，arr[7]=21 大于 arr[8]=17 下坡，r 收到 7。此时 l=r=7，循环停，返回 7，即峰顶 21 的位置。

下坡那步减一，峰就被顺手丢了

最容易栽的是下坡那支写成 r=mid-1：mid 自己可能就是峰顶，减一把它排除，收敛的位置就偏左一格、错过真正的峰。循环条件也别写成 l 不大于 r——用 r=mid 收缩时一旦 l==r，mid 仍等于 l、区间缩不动，就成死循环。还有个隐蔽点：本题没有 target，别拿 arr[mid] 和某个目标值比，方向全由相邻两格谁大谁小定。

复杂度上，每轮砍掉一半，n 个数最多比约 log₂n 次，时间 O(log n)；只用 l、r、mid 三个下标，空间 O(1)。

Python

def peakIndexInMountainArray(arr):
    l, r = 0, len(arr) - 1
    while l < r:                  # 区间收成一点就停
        mid = (l + r) // 2
        if arr[mid] < arr[mid + 1]:  # 上坡
            l = mid + 1            # 峰顶在右，丢左半
        else:                      # 下坡或正是峰顶
            r = mid                # 峰顶在左或就是它
    return l                       # l == r 即峰顶

C++

int peakIndexInMountainArray(vector<int>& arr){
    int l = 0, r = arr.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (arr[mid] < arr[mid + 1]) l = mid + 1;
        else r = mid;
    }
    return l;
}

Java

public int peakIndexInMountainArray(int[] arr) {
    int l = 0, r = arr.length - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (arr[mid] < arr[mid + 1]) l = mid + 1;
        else r = mid;
    }
    return l;
}