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。
题目给出的数据约束（来源：README）：
3 <= 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）的前提下，最大的边是c，a + 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，而是复用了手写的快速排序函数quickSort164：
func quickSort164(a []int, lo, hi int) { if lo >= hi { return } p := partition164(a, lo, hi) quickSort164(a, lo, p-1) quickSort164(a, p+1, 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[i+1], a[hi] = a[hi], a[i+1] return i + 1 }这是经典的原地快速排序实现：
partition164以最后一个元素为基准pivot，通过双指针原地分区，将小于pivot的元素交换到左侧，最后把pivot归位并返回其下标p；quickSort164递归对[lo, p-1]与[p+1, 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 -covermode=atomic -coverprofile=coverage.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），仅供参考
