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-GoLeetCode 题解的 Go 实现集合中的完整源码、单元测试与仓库工程规范讲解峰值元素问题的数学本质、两种二分查找解法的边界处理细节以及与第 852 题的异同。读完本文你将掌握如何在任意形状多峰的数组中用 O(logN) 复杂度定位任一峰值下标并理解这类局部极值二分题型的通用套路。题目理解峰值元素的定义与隐含条件原文档 leetcode/0162.Find-Peak-Element/README.md 给出的题目定义如下峰值元素是指其值大于左右相邻值的元素。给定一个输入数组nums其中nums[i] ≠ nums[i1]找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。你可以假设nums[-1] nums[n] -∞。拆解关键约束峰值定义下标i满足nums[i] nums[i-1]且nums[i] nums[i1]在数组边界处只比较存在的一侧。相邻不等nums[i] ≠ nums[i1]保证数组中不存在相邻相等元素这是二分能稳定收缩区间的前提。多峰值数组可以呈现锯齿状多次起伏返回值只需命中任意一个峰。虚拟边界nums[-1] nums[n] -∞这一假设非常关键它保证了一个数学结论——任何非空数组一定至少存在一个峰值最大值点必是峰值或位于单调区间端点。复杂度硬性要求题目 Note 明确要求O(logN)因此直接扫描全数组的 O(N) 线性解不合题意必须使用二分查找。原文档给出的两个示例输入输出说明[1,2,3,1]2元素3是峰值返回下标 2[1,2,1,3,5,6,4]1或5元素2下标 1与6下标 5都是峰值返回任意一个即可从朴素扫描到二分为什么 O(N) 不够最容易想到的解法是顺序扫描遍历每个下标判断nums[i]是否严格大于左右邻居找到第一个满足条件的位置返回。其时间复杂度为 O(N)在数据量达到十万、百万级时与 O(logN) 的二分差距是数量级的。但这道题真正的难点在于普通二分依赖有序数组而本数组整体无序。为什么还能二分核心在于题目只要求随便一个峰值而非最大值/最小值或指定目标值。结合虚拟边界nums[-1] nums[n] -∞我们可以对任意一个中点mid做局部判断若nums[mid] nums[mid1]说明中点右侧正在下坡而左边界是-∞则区间[low, mid]内必然存在一个峰值若nums[mid] nums[mid1]说明中点右侧在上坡而右边界是-∞则区间[mid1, 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[mid1] 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[mid1] 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[mid1] { high mid } else { low mid 1 } } return low }这段代码只有十来行却蕴含完整的正确性证明其核心观察是nums[mid] nums[mid1]下山段因为左端是-∞从low到mid这一段必然存在至少一个峰值收缩为high mid注意保留mid因为mid本身可能是峰值nums[mid] nums[mid1]上山段因为右端是-∞从mid1到high这一段必然存在至少一个峰值收缩为low mid 1mid不可能是峰值因为右侧更大。循环条件low high保证区间始终至少有两个元素因此mid1不会越界最终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[mid1] A[mid] A[mid-1] { res mid break } if A[mid] A[mid1] A[mid] A[mid-1] { high mid - 1 } if A[mid] A[mid1] 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[mid1] { high mid } else { low mid 1 } } return low }两题的对比结论清晰维度852山脉数组162峰值元素峰值数量唯一先升后降可能多个相邻不等假设成立成立nums[i] ≠ nums[i1]解法一代码三分支判断A[mid-1]与A[mid1]边界防御式三条件命中判断解法二代码low high 单次相邻比较完全一致核心思想向更高方向收缩向更高方向收缩从源码结构看两题的解法二几乎是逐行相同的验证了原文档搜索代码一样的判断——只要允许返回任意一个峰值多峰并不会给二分增加任何额外复杂度。单元测试边界情况的完整覆盖仓库为本题提供了完整的表驱动测试 162. Find Peak Element_test.go覆盖了以下输入输入数组期望输出覆盖的边界场景[2, 1, 2]0两侧都是峰取左侧峰[3, 2, 1]0严格递减左边界即峰[1, 2]1严格递增且长度为 2[2, 1]0严格递减且长度为 2[1]0单元素数组[1, 2, 3, 1]2题目示例 1[1, 2, 1, 3, 5, 6, 4]5题目示例 2多峰取右峰[1, 1]-1相邻相等违反题设验证兜底行为测试结构遵循本仓库统一的表驱动风格定义para162参数、ans162期望答案与question162组合结构遍历用例执行findPeakElement结果不匹配时通过t.Fatalf输出findPeakElement(%v) %d, want %d终止测试同时每个用例还会调用一次findPeakElement1验证第二种解法不 panic、逻辑正常。测试运行方式与其他题目一致在仓库根目录执行go test ./leetcode/0162.Find-Peak-Element/ -v -run Test_Problem162 -count1若需要生成全仓库覆盖率报告仓库提供了脚本 gotest.sh其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...项目以 go.modmodule github.com/halfrost/LeetCode-GoGo 1.19管理模块依赖题解包之间通过本地replace指令引用structures、template等公共包。复杂度与边界总结时间复杂度两种解法均为 O(logN)。每次迭代将搜索区间缩小约一半最多执行log2(n)次比较。空间复杂度O(1)仅使用low、high、mid三个指针变量无额外数据结构。关键边界处理清单空数组 / 单元素数组解法一提前返回0左边界结合nums[-1] -∞只需比较nums[1] nums[0]右边界结合nums[n] -∞只需比较nums[n-1] nums[n]严格递增[1,2]解法二循环low0, high1mid0nums[0] nums[1]low1返回1严格递减[2,1]mid0nums[0] nums[1]high0返回0相邻相等违反题设题目明确nums[i] ≠ nums[i1]测试中的[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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考