わたしの部屋

范围#

题型归纳#

题型： 二分找局部最优

特征： 要找任意一个峰值，且相邻元素不相等。

解法： 根据 mid 左右的上升、下降趋势判断哪一侧一定存在峰值。

易错点： 边界位置要单独判断，避免访问越界。

峰值不要求全局最大，只要找到一个局部极大值就行——这是二分能介入的关键信号。两端各有一个隐含的 -∞ 边界，保证了峰值一定存在。先单独判断首尾，剩下的安全区间 [1, n-2] 才交给二分，每次根据 mid 左右的斜率方向缩小范围；最容易出错的是直接从 [0, n-1] 开始二分，循环体内访问 arr[m-1] 或 arr[m+1] 时越界。

题意#

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例#

示例 1：

输入： nums = [1,2,3,1]

输出： 2

解释： 3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入： nums = [1,2,1,3,5,6,4]

输出： 1 或 5

解释： 你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5，其峰值元素为 6。

提示#

• 1 <= nums.length <= 1000
• -2^31 <= nums[i] <= 2^31 - 1
• 对于所有有效的 i 都有 nums[i] != nums[i + 1]

核心思路#

把数组看成一段连续的山坡。因为题目默认 nums[-1] = nums[n] = -∞，并且相邻元素不相等，所以数组中一定存在峰值。

先单独判断两个边界：

• 如果 arr[0] > arr[1]，那么 0 位置就是峰值。
• 如果 arr[n - 1] > arr[n - 2]，那么 n - 1 位置就是峰值。

排除边界后，峰值一定在 [1, n - 2] 范围内。对中点 m 做判断：

• 如果 arr[m - 1] > arr[m]，说明左侧存在上坡，往左找。
• 如果 arr[m] < arr[m + 1]，说明右侧存在上坡，往右找。
• 否则 arr[m] 同时大于左右相邻值，m 就是峰值。

沿任意上升方向走，一定能到达峰值——因为数组两端被 -∞ 封住，上坡不可能无限延伸。

核心模板#

1
public static int findPeakElement(int[] arr) {
2
    int n = arr.length;
3
    if (n == 1) {
4
        return 0;
5
    }
6
    if (arr[0] > arr[1]) {
7
        return 0;
8
    }
9
    if (arr[n - 1] > arr[n - 2]) {
10
        return n - 1;
11
    }
12
    int l = 1, r = n - 2, m = 0, ans = -1;
13
    while (l <= r) {
14
        m = (l + r) / 2;
15
        if (arr[m - 1] > arr[m]) {
16
            r = m - 1;
17
        } else if (arr[m] < arr[m + 1]) {
18
            l = m + 1;
19
        } else {
20
            ans = m;
21
            break;
22
        }
23
    }
24
    return ans;
25
}

变量角色#

l 和 r 是二分的左右边界，初始锁定在安全区间 [1, n-2] 内；m 是每轮的中点；ans 记录找到的峰值下标，初始为 -1，找到后立即跳出循环。

过程拆解#

1. 特判：长度为 1 时直接返回 0。
2. 首尾判断：检查 arr[0] 和 arr[n-1] 是否为峰值，是则提前返回。
3. 二分：在安全区间 [1, n-2] 内取中点 m，比较 arr[m-1]、arr[m]、arr[m+1] 三者关系。
4. 收边界：左侧下降则往左收，右侧上升则往右收，两侧都不满足则 m 即为峰值。

易错点#

二分区间的边界陷阱

错误写法：直接从 [0, n-1] 开始二分，循环体内同时访问 arr[m-1] 和 arr[m+1]：

1
int l = 0, r = n - 1;
2
while (l <= r) {
3
    m = (l + r) / 2;
4
    if (arr[m - 1] > arr[m]) { // m == 0 时，arr[-1] 越界！
5
        r = m - 1;
6
    } else if (arr[m] < arr[m + 1]) { // m == n-1 时，arr[n] 越界！
7
        l = m + 1;
8
    } else {
9
        return m;
10
    }
11
}

为什么错：m 可能取到 0 或 n-1，访问 arr[-1] 或 arr[n] 时直接抛出 ArrayIndexOutOfBoundsException。

正确写法一：先处理首尾，再从 [1, n-2] 开始二分（即本文模板）。

正确写法二：换成只比较 arr[m] 和 arr[m+1] 的写法，配合 while (l < r)——此时 m 永远小于 r，m+1 不会越界：

1
public int findPeakElement(int[] nums) {
2
    int l = 0, r = nums.length - 1;
3
    while (l < r) {
4
        int m = l + (r - l) / 2;
5
        if (nums[m] > nums[m + 1]) {
6
            r = m;
7
        } else {
8
            l = m + 1;
9
        }
10
    }
11
    return l;
12
}

口诀

先判首尾，再在 [1, n-2] 内二分，靠斜率方向收边界。