LeetCode 162. 寻找峰值

◎

本节目标

根据相邻元素的局部升降趋势，二分保留必然存在峰值的一侧。

这道题说明二分查找解题框架不要求整体有序：局部升降方向已经足以证明一侧仍存在峰值。

查看原题

题意与约束

峰值严格大于左右相邻元素；数组两端外侧视为负无穷。相邻元素不相等，返回任意一个峰值下标即可。

朴素思路与瓶颈

线性检查每个位置与相邻元素能在 O(n) 内找到峰值；先找全局最大值也仍需完整扫描。相邻元素不相等，使中点处的上升或下降方向足以保证一侧存在峰值，可以用二分降到 O(log n)。

从坡度保留候选

比较 nums[mid] 与 nums[mid + 1]：

• 若正在上升，右侧至少能沿上升走到一个峰值，保留 [mid + 1, right]；
• 否则正在下降，左侧包含 mid 的区域一定能到达峰值，保留 [left, mid]。

这不是在断言整个数组单调，而是在每一步用相邻关系证明被保留侧至少有一个峰值。循环使用 left < right，因此 mid + 1 始终在数组范围内；最终单点就是一个可返回的峰值。

代码实现

测试只验证返回下标确实满足峰值定义，从而允许多峰数组返回不同的合法答案。

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;
        while (left < right) {
            const int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

Python

Python 3

class Solution:
    def findPeakElement(self, nums):
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left

复杂度分析

• 时间复杂度：O(log n)。
• 空间复杂度：O(1)。

易错点

• 不要要求返回全局最大值；任意峰值都正确。
• 上升时必须丢掉 mid，下降时必须保留 mid。
• 单元素数组自然是峰值，循环不会进入并返回下标 0。

模式迁移

这类题训练的是“局部比较能推出存在性”的证明方式；以后遇到单峰函数或局部最优结构，也先寻找可安全排除一侧的证据。