LeetCode-Go 题解：162. Find Peak Element 寻找峰值元素的 O(logN) 二分实现

LeetCode-Go 题解：162. Find Peak Element 寻找峰值元素的 O(logN) 二分实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文以 LeetCode 第 162 题「寻找峰值元素」为核心，结合开源仓库 LeetCode-Go（LeetCode 题解的 Go 实现集合）中的完整源码、单元测试与仓库工程规范，讲解峰值元素问题的数学本质、两种二分查找解法的边界处理细节，以及与第 852 题的异同。读完本文，你将掌握如何在任意形状（多峰）的数组中用 O(logN) 复杂度定位任一峰值下标，并理解这类"局部极值二分"题型的通用套路。

题目理解：峰值元素的定义与隐含条件

原文档 leetcode/0162.Find-Peak-Element/README.md 给出的题目定义如下：

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组nums，其中nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设nums[-1] = nums[n] = -∞。

拆解关键约束：

• 峰值定义：下标i满足nums[i] > nums[i-1]且nums[i] > nums[i+1]（在数组边界处只比较存在的一侧）。
• 相邻不等：nums[i] ≠ nums[i+1]保证数组中不存在相邻相等元素，这是二分能稳定收缩区间的前提。
• 多峰值：数组可以呈现"锯齿状"多次起伏，返回值只需命中任意一个峰。
• 虚拟边界：nums[-1] = nums[n] = -∞这一假设非常关键，它保证了一个数学结论——任何非空数组一定至少存在一个峰值（最大值点必是峰值，或位于单调区间端点）。
• 复杂度硬性要求：题目 Note 明确要求O(logN)，因此直接扫描全数组的 O(N) 线性解不合题意，必须使用二分查找。

原文档给出的两个示例：

从朴素扫描到二分：为什么 O(N) 不够

最容易想到的解法是顺序扫描：遍历每个下标，判断nums[i]是否严格大于左右邻居，找到第一个满足条件的位置返回。其时间复杂度为 O(N)，在数据量达到十万、百万级时，与 O(logN) 的二分差距是数量级的。

但这道题真正的难点在于：普通二分依赖"有序数组"，而本数组整体无序。为什么还能二分？核心在于题目只要求"随便一个峰值"，而非"最大值/最小值"或"指定目标值"。结合虚拟边界nums[-1] = nums[n] = -∞，我们可以对任意一个中点mid做局部判断：

• 若nums[mid] > nums[mid+1]，说明中点右侧正在下坡，而左边界是-∞，则区间[low, mid]内必然存在一个峰值；
• 若nums[mid] < nums[mid+1]，说明中点右侧在上坡，而右边界是-∞，则区间[mid+1, high]内必然存在一个峰值。

这种"根据相邻元素比较结果决定舍弃哪一半"的二分，本质是局部极值搜索，不要求数组整体有序，是二分思想在非单调序列上的经典扩展。

解法一：边界防御式二分（仓库源码逐行解析）

仓库源码 162. Find Peak Element.go 提供了两种实现。第一种findPeakElement是"防御式"写法，对大量边界情况做了显式判断，适合理解题目所有边界条件：

// 解法一 二分 func findPeakElement(nums []int) int { if len(nums) == 0 || len(nums) == 1 { return 0 } low, high := 0, len(nums)-1 for low <= high { mid := low + (high-low)>>1 if (mid == len(nums)-1 && nums[mid-1] < nums[mid]) || (mid > 0 && nums[mid-1] < nums[mid] && (mid <= len(nums)-2 && nums[mid+1] < nums[mid])) || (mid == 0 && nums[1] < nums[0]) { return mid } if mid > 0 && nums[mid-1] < nums[mid] { low = mid + 1 } if mid > 0 && nums[mid-1] > nums[mid] { high = mid - 1 } if mid == low { low++ } if mid == high { high-- } } return -1 }

逐段拆解这段代码的设计意图：

1. 空数组与单元素提前返回

if len(nums) == 0 || len(nums) == 1 { return 0 }

长度为 0 或 1 时，数组退化，唯一元素（或空）直接视为峰值位置返回0。注意：返回0对空数组而言是一种约定俗成的兜底，因为空数组严格来说没有合法下标。

2. 峰值命中条件的三种分支

mid处于数组三个位置时需要分别判定：

• mid == len(nums)-1（右边界）：只需验证nums[mid-1] < nums[mid]，结合假设nums[n] = -∞，右侧必小于nums[mid]；
• 0 < mid < len(nums)-1（中间）：需要nums[mid-1] < nums[mid] && nums[mid+1] < nums[mid]同时成立，即严格大于左右邻居；
• mid == 0（左边界）：只需验证nums[1] < nums[0]，结合假设nums[-1] = -∞。

3. 区间收缩策略

当mid不是峰值时：

• 若nums[mid-1] < nums[mid]，说明左邻小于中点，峰值应向右寻找（上坡方向），low = mid + 1；
• 若nums[mid-1] > nums[mid]，说明左邻大于中点，峰值应向左寻找（下坡方向），high = mid - 1。

4. 防死循环的指针修正

if mid == low { low++ } if mid == high { high-- }

当区间长度收缩到 2 时，mid = low或mid = high可能使区间无法继续收缩，这里通过手动移动指针防止死循环。这是防御式写法为了覆盖所有极端输入（如严格递增、严格递减、[2,1]、[1,2]等）付出的额外逻辑成本。

解法二：精简优雅的爬山式二分（推荐写法）

同一源码文件中的findPeakElement1是更简洁、也更适合面试与工程实践的版本：

// 解法二 二分 func findPeakElement1(nums []int) int { low, high := 0, len(nums)-1 for low < high { mid := low + (high-low)>>1 // 如果 mid 较大，则左侧存在峰值，high = m，如果 mid + 1 较大，则右侧存在峰值，low = mid + 1 if nums[mid] > nums[mid+1] { high = mid } else { low = mid + 1 } } return low }

这段代码只有十来行，却蕴含完整的正确性证明，其核心观察是：

• nums[mid] > nums[mid+1]（下山段）：因为左端是-∞，从low到mid这一段必然存在至少一个峰值，收缩为high = mid（注意保留mid，因为mid本身可能是峰值）；
• nums[mid] < nums[mid+1]（上山段）：因为右端是-∞，从mid+1到high这一段必然存在至少一个峰值，收缩为low = mid + 1（mid不可能是峰值，因为右侧更大）。

循环条件low < high保证区间始终至少有两个元素，因此mid+1不会越界；最终low与high收敛到同一个下标，即为一个峰值。整个过程可以形象地理解为"爬山"：从区间中点出发，永远向着海拔更高的方向走，由于两端都是-∞，必然能登上一座山峰。

这种写法在仓库第 852 题中也有对应版本（见下文对比），属于本仓库在"峰值系列"题目中反复使用的统一模式。

与第 852 题的关联：一峰与多峰的统一解法

原文档解题思路中明确指出："这一题是第 852 题的伪加强版，第 852 题中只存在一个山峰，这一题存在多个山峰。但是实际上搜索的代码是一样的，因为此题只要求随便输出一个山峰的下标即可。"

对比仓库中第 852 题 852. Peak Index in a Mountain Array.go 的两种实现：

// 解法一 二分 func peakIndexInMountainArray(A []int) int { res, low, high := 0, 0, len(A)-1 for low <= high { mid := low + (high-low)>>1 if A[mid] > A[mid+1] && A[mid] > A[mid-1] { res = mid break } if A[mid] > A[mid+1] && A[mid] < A[mid-1] { high = mid - 1 } if A[mid] < A[mid+1] && A[mid] > A[mid-1] { low = mid + 1 } } return res } // 解法二 二分 func peakIndexInMountainArray1(A []int) int { low, high := 0, len(A)-1 for low < high { mid := low + (high-low)>>1 if A[mid] > A[mid+1] { high = mid } else { low = mid + 1 } } return low }

两题的对比结论清晰：

从源码结构看，两题的"解法二"几乎是逐行相同的，验证了原文档"搜索代码一样"的判断——只要允许返回任意一个峰值，多峰并不会给二分增加任何额外复杂度。

单元测试：边界情况的完整覆盖

仓库为本题提供了完整的表驱动测试 162. Find Peak Element_test.go，覆盖了以下输入：

测试结构遵循本仓库统一的表驱动风格：定义para162（参数）、ans162（期望答案）与question162（组合结构），遍历用例执行findPeakElement，结果不匹配时通过t.Fatalf输出findPeakElement(%v) = %d, want %d终止测试；同时每个用例还会调用一次findPeakElement1验证第二种解法不 panic、逻辑正常。

测试运行方式与其他题目一致，在仓库根目录执行：

go test ./leetcode/0162.Find-Peak-Element/ -v -run Test_Problem162 -count=1

若需要生成全仓库覆盖率报告，仓库提供了脚本 gotest.sh，其核心命令为：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

项目以 go.mod（module github.com/halfrost/LeetCode-Go，Go 1.19）管理模块依赖，题解包之间通过本地replace指令引用structures、template等公共包。

复杂度与边界总结

时间复杂度：两种解法均为 O(logN)。每次迭代将搜索区间缩小约一半，最多执行log2(n)次比较。

空间复杂度：O(1)，仅使用low、high、mid三个指针变量，无额外数据结构。

关键边界处理清单：

1. 空数组 / 单元素数组：解法一提前返回0；
2. 左边界：结合nums[-1] = -∞，只需比较nums[1] < nums[0]；
3. 右边界：结合nums[n] = -∞，只需比较nums[n-1] < nums[n]；
4. 严格递增[1,2]：解法二循环low=0, high=1，mid=0，nums[0] < nums[1]，low=1，返回1；
5. 严格递减[2,1]：mid=0，nums[0] > nums[1]，high=0，返回0；
6. 相邻相等（违反题设）：题目明确nums[i] ≠ nums[i+1]，测试中的[1,1]用例用于验证实现的兜底行为。

实战启发：峰值二分模式的推广

本题的核心方法论——"向海拔更高的邻居方向收缩区间"——不止适用于本题，可推广到一类"局部极值"问题：

• 852. Peak Index in a Mountain Array：单峰山脉数组求峰顶，代码与本题解法二完全同构；
• 153 / 154. 旋转排序数组求最小值：通过比较nums[mid]与边界值判断旋转点在左半还是右半，同样依赖"必存在极值"的区间收缩论证；
• 658. 查找 K 个最接近元素、875. 爱吃香蕉的珂珂等题目，也都用到了"比较中点邻居后收缩区间"的二分变体。

掌握 162 题的两种实现，就等于掌握了这类"无序数组中找极值"问题的标准模板：先用端点假设（±∞）确认解必存在，再用相邻比较确定收缩方向，最后用low < high的循环不变量保证收敛。这也是 LeetCode-Go 仓库将多种解法与完整测试一并收录的价值所在——读者可以从 leetcode/0162.Find-Peak-Element 目录出发，对比不同写法的取舍，建立自己的二分边界处理直觉。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go