0162. Find Peak Element ======================= 题目信息 -------- :题号: 0162. 寻找峰值 :难度: Medium :主题: 数组、二分查找、局部单调性 :原题: `LeetCode 0162 `_ :重点: 从逐点验证峰值,推导到用一条相邻斜率保留必含峰值的区间 题目重述 -------- 给定整数数组 ``nums``,相邻元素互不相等。若 ``nums[i]`` 严格大于它的左右邻居, 则下标 ``i`` 是峰值。数组两端之外视为负无穷,因此首、尾元素也可能成为峰值。 数组至少含一个元素,可能存在多个峰值;返回任意一个峰值的下标,并将时间复杂度控制在 ``O(log n)``。 自建示例 -------- .. code-block:: text 输入:nums = [1,3,2,5,4] 输出:1 或 3 下标 1 和 3 都高于各自的两个邻居,返回其中任意一个都满足题意。 .. code-block:: text 输入:nums = [8,5,2] 输出:0 8 大于右邻居 5,左侧边界又是负无穷,所以首元素就是峰值。 .. code-block:: text 输入:nums = [6] 输出:0 唯一元素的两侧都是虚拟的负无穷。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: int linearFirstDescent(const std::vector& nums) { int size = static_cast(nums.size()); for (int i = 0; i + 1 < size; ++i) { if (nums[i] > nums[i + 1]) { return i; } } return size - 1; } int binaryBySlope(const std::vector& nums) { int left = 0; int right = static_cast(nums.size()) - 1; while (left < right) { int middle = left + (right - left) / 2; if (nums[middle] < nums[middle + 1]) { left = middle + 1; } else { right = middle; } } return left; } public: int findPeakElement(std::vector& nums) { return binaryBySlope(nums); } }; 题解 ---- 原始任务是逐点验证 ~~~~~~~~~~~~~~~~~~ 按照定义,可以依次检查每个下标是否同时高于左右邻居。这一定正确,却需要最坏 ``O(n)`` 次检查,而且每个内部位置会反复参与左右两次比较。 把观察单位从“一个点的两个邻居”改成“一对相邻元素”,线性扫描已经能减少思考: * 找到第一条下降边 ``nums[i] > nums[i + 1]`` 时,``i`` 就是峰值。若 ``i > 0``, 此前没有下降边且相邻值不等,所以 ``nums[i - 1] < nums[i]``;若 ``i = 0``, 左侧是负无穷; * 若一直没有下降,数组严格上升到末尾,末元素就是峰值。 ``linearFirstDescent`` 实现了这个基线方案。它说明寻找峰值不必完整比较每个点, 但仍可能走完整个数组。 一条斜率能排除哪一半 ~~~~~~~~~~~~~~~~~~~~~~ 比较中点 ``middle`` 与它的右邻居,只会出现两种情况: * ``nums[middle] < nums[middle + 1]``:这里正在上坡。从 ``middle + 1`` 继续向右, 要么以后出现第一条下降边,其左端是峰值;要么一路上升到有效区间右端。因此保留 ``[middle + 1, right]``; * ``nums[middle] > nums[middle + 1]``:这里正在下坡。反向向左使用同一论证, ``[left, middle]`` 中必有峰值;``middle`` 自己仍可能是峰值,不能写成 ``right = middle - 1``。 相邻元素不相等非常关键:比较结果不会出现平台。若允许相等,仅凭一条水平边无法判断 哪一侧必有严格峰值。 区间不变量 ~~~~~~~~~~ 二分区间不表示峰值已经确定,而表示“区间内至少存在一个峰值”。可以用两条边界斜率 把这件事说得更精确: * 若 ``left > 0``,则区间从左边界外向内上升,即 ``nums[left - 1] < nums[left]``; * 若 ``right + 1 < n``,则区间从内部向右边界外下降,即 ``nums[right] > nums[right + 1]``。 初始区间借助两侧的负无穷满足这个条件。遇到上坡并令 ``left = middle + 1``, 这条上坡正好成为新的左边界保证;遇到下坡并令 ``right = middle``,这条下坡正好成为 新的右边界保证。因此每次删除一半旧搜索区间后,不变量仍成立。 当 ``left == right`` 时,只剩一个位置。左边界保证它高于左邻居,右边界保证它高于 右邻居,缺失的邻居则由负无穷补足,所以该位置必为峰值。 具体走读 ~~~~~~~~ 对 ``[1,3,2,5,4]``: #. 初始 ``[left,right] = [0,4]``,``middle = 2``;``2 < 5`` 是上坡,峰值必在 右侧,令 ``left = 3``。待搜索区间成为 ``[3,4]``; #. 此时 ``middle = 3``;``5 > 4`` 是下坡,保留可能成为峰值的 ``middle``,令 ``right = 3``; #. 区间收缩到下标 3。它左侧由第一轮的上坡保证更小,右侧由第二轮的下坡保证更小, 因而返回 3。 对严格下降的 ``[8,5,2]``,每轮都走 ``right = middle``,最终停在下标 0; 对单元素数组,循环根本不执行,初始位置直接返回。``middle + 1`` 始终安全,因为只有 ``left < right`` 时才计算中点,此时 ``middle < right``。 方案选择与复杂度 ~~~~~~~~~~~~~~~~ 线性方案的证明直观,时间为 ``O(n)``、额外空间为 ``O(1)``;二分方案把“继续走到峰值” 压缩为“根据当前斜率删除不可能需要保留的一半区间”,时间降为 ``O(log n)``,额外空间 仍为 ``O(1)``。题目明确要求对数时间,因此 ``binaryBySlope`` 是主解。