寻找峰值 图解题解

寻找峰值到底要我返回哪个下标

给一个数组 nums，峰值指严格大于左右两个邻居的位置，两端之外看作负无穷，题目保证相邻不相等。要返回任意一个峰值下标，可能有多个峰，返回哪个都对。题面 nums=[1,3,5,7,9,11,13,15,17,16,14,12,10] 在下标 8 处的 17 比左右都高，返回 8。因为两端是负无穷，哪怕数组一路涨，末位也算峰，峰必存在。

从头扫一遍要 O(n)，凭什么能更快

线性做法一眼能想到：从左往右扫，逐个查谁比左右都高，撞到第一个就返回。它对，但题目说能在 O(log n) 内完成，扫一遍是线性的、太亏。数组根本没排序、忽高忽低，而二分查找通常要求有序，凭什么把 O(n) 压成 O(log n)？

数组无序，凭什么还能对半砍

能砍的底气来自一个爬坡直觉。看任意下标和它右邻居谁高：右邻居更高就是上坡（此刻在往上走），顺上坡往右，坡不能无限升，右端外是负无穷，早晚掉头，那个由升转降的转折点就是峰。所以朝更高的一侧走，前方必有峰；右邻居更矮则是下坡，峰在左侧，当前位置也可能就是峰顶。每比一次就能定下峰在哪半边、扔掉另一半。二分要的不是「有序」，而是「哪半边一定有解」，本题用负无穷的边界凑齐了它。

拿 mid 和右邻居比，往哪半边收

左指针 l 从 0、右指针 r 从 n-1 起，区间 [l, r]。每轮取正中下标 mid=(l+r)//2，比 nums[mid] 和右邻居 nums[mid+1]：前者小是上坡，峰在右，左边界推到 l=mid+1，mid 矮当不了峰一并丢；否则是下坡，峰在左半段且可能就是 mid，右边界收成 r=mid、保留 mid。统一比右邻居还躲开越界：l<r 时 mid 最多 r-1，mid+1 不越界。收到 l==r 缩成一点，那下标就是峰值。

示例这串数，l 和 r 怎么夹到下标 8

就拿题面这串，n=13。l=0、r=12：mid=6，nums[6]=13 小于 nums[7]=15，上坡，l=7。l=7、r=12：mid=9，nums[9]=16 大于 nums[10]=14，下坡，r=9。l=7、r=9：mid=8，nums[8]=17 大于 nums[9]=16，下坡，r=8。l=7、r=8：mid=7，nums[7]=15 小于 nums[8]=17，上坡，l=8。l==r==8，返回 8，即 nums[8]=17。

收反方向，峰值当场从眼皮底下漏掉

最刺眼的坑是把收缩方向反了：上坡本该往右，若当成峰在左、朝更矮一侧收，峰当场从眼皮底下漏掉。循环开闭也易写坏，得写 while l<r 配 r=mid：若写成 l<=r，收缩到 l==r 时循环不停，又取一次 mid==l、下坡分支再令 r=mid，两指针原地不动，卡成死循环。还有 mid 写成 (l+r) 再除，l、r 很大时会溢出，改 l+(r-l)//2 先求差再折半就不会爆。整个过程每轮把区间砍一半，最多 log n 轮收敛到一点，时间 O(log n)；只用 l、r、mid 三个变量，空间 O(1)。

Python

def findPeakElement(nums):
    l, r = 0, len(nums) - 1        # 搜索区间 [l, r]
    while l < r:
        mid = (l + r) // 2
        if nums[mid] < nums[mid + 1]:  # 上坡，峰在右
            l = mid + 1
        else:                          # 下坡，峰在左(含 mid)
            r = mid
    return l                        # l == r 即峰值下标

C++

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

Java

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