LeetCode-Go 题解：976. Largest Perimeter Triangle（最大周长三角形，排序 + 贪心判定）

LeetCode-Go 题解976. Largest Perimeter Triangle最大周长三角形排序 贪心判定【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 976 题「Largest Perimeter Triangle最大周长三角形」展开以 LeetCode-Go 仓库中该题的 README 题解 为骨架深入讲解排序 贪心枚举的解题思路并对照仓库中的 Go 源码实现 与 单元测试 逐行剖析。读完本文你将掌握三角形三边判定条件的两种等价写法、降序枚举的贪心正确性证明以及手写快速排序在仓库中如何被复用能够独立写出时间复杂度和空间复杂度均可控的 Go 解法。一、题目回顾与数据范围原题要求如下给定一个由正数长度组成的数组A从中选取 3 条边组成一个面积非零的三角形返回能组成的三角形中最大的周长如果任意 3 条边都无法组成面积非零的三角形返回 0。题目给出的数据约束来源README3 A.length 100001 A[i] 10^6由数据范围可知数组规模最大 10000值域最大 10^6采用基于比较的排序O(n log n)是完全可行的。官方示例题目原文共给出 4 组示例README输入输出说明[2,1,2]5取边 2、1、2满足三角形条件周长 5[1,2,1]0任意三边组合都无法构成面积非零三角形[3,2,3,4]10取边 3、3、4周长 10[3,6,2,3]8取边 3、3、2周长 8其中第 4 个示例尤其值得注意数组[3,6,2,3]中最大的三条边是 6、3、3但3 3 6恰好退化成面积为零的退化三角形因此必须放弃最大边 6退而选择 3、3、2 这三条边得到周长 8。这个示例直观说明了为何不能直接取最大的三条边。二、解题思路排序 贪心枚举2.1 三角形判定条件三条线段a b c能构成面积非零三角形的充要条件是任意两边之和大于第三边即同时满足a b ca c bb c a不过在三边已排序a b c的前提下最大的边是ca c b与b c a恒成立真正需要检验的只有a b c这一个不等式。2.2 贪心策略与正确性README 解题思路 给出的方案是先将所有长度进行排序从大边开始往前找找到第一个满足任意两边之和大于第三边即能构成三角形的连续三边下标输出这 3 条边之和即为最大周长若找不到输出 0。为什么从大到小枚举连续的三元组就能得到全局最大周长核心在于贪心正确性排序后数组为A[0] A[1] ... A[n-1]若降序扫描到下标i时A[i-2] A[i-1] A[i]成立则(A[i-2], A[i-1], A[i])是合法三角形此时A[i]是能作为最大边的所有候选边中的最大值因为任何包含比A[i]更大边的组合都不可能比它周长更大对于以A[i]为最大边的组合A[i-1]与A[i-2]已经是除A[i]外剩余元素中最大的两个因此该组合是该最大边下周长最大的选择若A[i-2] A[i-1] A[i]则任何更小的两条边A[j] A[k]其中j, k i-1只会更小更不可能构成三角形因此可以直接跳过A[i]继续向前。综上第一次命中条件的连续三元组即全局最优解无需回溯一次线性扫描即可完成。2.3 退化三角形的处理注意题目要求非零面积。当出现A[i-2] A[i-1] A[i]时三边共线、面积为 0必须视为不合法并继续向前扫描。这正是示例 4 中[3, 6, 2, 3]排完序为[2, 3, 3, 6]后最大边 6 与 3、3 组合因3 3 6被否决的原因。三、仓库源码逐行剖析仓库中的核心实现位于 leetcode/0976.Largest-Perimeter-Triangle/976. Largest Perimeter Triangle.go主函数如下func largestPerimeter(A []int) int { if len(A) 3 { return 0 } quickSort164(A, 0, len(A)-1) for i : len(A) - 1; i 2; i-- { if (A[i]A[i-1] A[i-2]) (A[i]A[i-2] A[i-1]) (A[i-2]A[i-1] A[i]) { return A[i] A[i-1] A[i-2] } } return 0 }该实现有几个值得注意的细节边界保护len(A) 3时直接返回 0与题目3 A.length的约束保持一致属于防御性编码。三条件全量判定虽然排序后只需判断A[i-2]A[i-1] A[i]但仓库实现同时写全了三个不等式。这种写法不依赖已排序这一隐含前提语义上更贴近三角形判定的原始定义可读性更好逻辑上完全等价且不损失性能。降序扫描for i : len(A) - 1; i 2; i--从最大边开始命中即返回保证返回的是最大周长。3.1 手写快速排序 quickSort164有趣的是仓库并没有调用标准库sort而是复用了手写的快速排序函数quickSort164func quickSort164(a []int, lo, hi int) { if lo hi { return } p : partition164(a, lo, hi) quickSort164(a, lo, p-1) quickSort164(a, p1, hi) } func partition164(a []int, lo, hi int) int { pivot : a[hi] i : lo - 1 for j : lo; j hi; j { if a[j] pivot { i a[j], a[i] a[i], a[j] } } a[i1], a[hi] a[hi], a[i1] return i 1 }这是经典的原地快速排序实现partition164以最后一个元素为基准pivot通过双指针原地分区将小于pivot的元素交换到左侧最后把pivot归位并返回其下标pquickSort164递归对[lo, p-1]与[p1, hi]两个子区间排序。从源码结构看该排序函数带有164后缀说明它最初在 164. Maximum Gap 题解 中被定义随后被 274. H-Index 题解 与本题 976 复用属于仓库内跨题复用的公共工具函数。这也解释了为什么题目 976 的排序逻辑没有额外引入标准库依赖。3.2 复杂度分析时间复杂度快速排序平均 O(n log n)最坏 O(n²)降序扫描 O(n)。整体为 O(n log n)。空间复杂度排序为原地操作交换元素递归栈深度平均 O(log n)最坏 O(n)无额外大数组分配。在n 10000、值域10^6的约束下该方案在时间与空间上都完全满足 LeetCode 的要求。四、测试用例与验证仓库为本题配套了完整的表格驱动测试 leetcode/0976.Largest-Perimeter-Triangle/976. Largest Perimeter Triangle_test.go共覆盖 7 组用例输入期望输出覆盖意图[1, 2]0元素不足 3 个防御分支[1, 2, 3]0恰好退化1 2 3[]0空数组边界[2, 1, 2]5官方示例 1[1, 1, 2]0退化三角形1 1 2[3, 2, 3, 4]10官方示例 3[3, 6, 2, 3]8官方示例 4最大边被否决测试框架采用 LeetCode-Go 仓库统一的question976/para976/ans976结构para承载输入参数ans承载期望答案通过largestPerimeter(p.one)与期望值比对。其中[1, 1, 2]与[1, 2, 3]两组用例专门验证了退化三角形面积为零不计入结果的边界逻辑是本题最容易写错的点。仓库在根目录 gotest.sh 中提供了统一的测试与覆盖率生成命令go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...在仓库根目录执行该命令即可运行全部 leetcode 目录下的测试包括本题并生成覆盖率文件与项目100% test coverage的目标保持一致。五、可运行的最小实现如果想脱离仓库单独理解本题可以基于上述思路写出最小实现以标准库排序为例import sort func largestPerimeter(nums []int) int { if len(nums) 3 { return 0 } sort.Ints(nums) // 升序排序 for i : len(nums) - 1; i 2; i-- { // 已排序时只需判断两条较小边之和大于最大边 if nums[i-2]nums[i-1] nums[i] { return nums[i] nums[i-1] nums[i-2] } } return 0 }该版本与仓库实现的核心算法完全一致升序排序 从大到小枚举连续三元组 首次命中即返回。区别仅在于仓库用自研quickSort164替代了标准库sort.Ints并在条件判定上写全了三个不等式以增强可读性。六、小结LeetCode 976 是一道典型的排序 贪心入门题其核心要点可以归纳为判定条件三角形任意两边之和大于第三边排序后可简化为两条较小边之和 最大边。贪心策略降序枚举连续三元组首次命中即为最大周长正确性由最大边优先 次大边组合最优保证。退化处理a b c时面积为 0必须排除示例 4 与测试用例[1, 1, 2]、[1, 2, 3]均针对此场景。实现细节参考 LeetCode-Go 仓库的 源码注意边界保护len 3返回 0、条件书写完整性以及跨题复用排序工具函数的组织方式。掌握本题后类似的最大/最小满足几何或数值约束的三元组问题如排序后双指针、贪心前缀和都可以套用先排序、再枚举、巧剪枝的通用范式。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考