力扣双周赛 120 第 2 题《找到最大周长的多边形》贪心 + 排序全解（附 Go 仓库源码级验证）

本篇技术指南围绕 LeetCode Biweekly Contest 120 第 2 题 Find Polygon with the Largest Perimeter 展开：从「排序 + 前缀和贪心」的核心思路出发，完整给出 Python / Java / C++ / Go 四语言可直接提交的实现，并结合当前仓库 codeforces-go 中 leetcode/biweekly/120/b/ 目录下的源码、测试用例与测试框架实现，验证算法的正确性与复杂度结论。读完本文，你将掌握一类「以最长边贪心构造多边形并求最大周长」的通用解法，并能看懂仓库中 LeetCode 题目的组织方式与自动化测试机制。

题目背景：什么样的边能组成多边形

本题要求从给定的正整数数组 nums 中选出尽可能多的边，构成一个周长最大的多边形。题目位于仓库 leetcode/biweekly/120/b/README.md，对应力扣题目 Find Polygon with the Largest Perimeter。

先回顾平面几何的基本事实：对于 n 边形（n >= 3），任意一条边的长度必须严格小于其余所有边的长度之和。等价地，若将边长按升序排列，则最大边必须满足：

最大边 < 其余所有边之和

这一点是整道题的出发点。仓库测试文件中的 URL 注释也印证了题目归属：

• b_test.go 中标注了 biweekly-contest-120 与题目 find-polygon-with-the-largest-perimeter。

核心思路：排序后枚举最长边，前缀和贪心

官方题解文档（即关联 README）给出的核心思路非常精炼：

把数组排序，枚举 nums[i] 作为最长的那条边，那么 nums[i] 左边的数之和越大越好，这样才能尽可能地组成多边形，并且周长尽量长。

推导逻辑如下：

1. 排序：先将 nums 升序排列。因为判断「某条边能否成为最长边」只需要关心比它小（或相等）的边，排序后前缀自然就是候选的其余边集合。
2. 贪心选择：对某个位置 i，nums[i] 左侧的数是所有比它小的数。为了尽可能组成多边形，左侧的所有数都要选上——因为 nums[i] 固定的前提下，其余边之和越大，越容易满足严格大于 nums[i] 的条件；同时选得越多，周长也越长。
3. 前缀和判定：遍历过程中维护前缀和 s，判断条件为：

nums[0] + nums[1] + ... + nums[i-1] > nums[i]

等价于 s - x > x，即 s > x * 2。最后一个满足该条件的 i，其前缀和

nums[0] + nums[1] + ... + nums[i-1] + nums[i]

就是答案。若没有任何位置满足条件，则返回 -1。

为什么"最后一个满足"就是最大周长：随着 i 增大，前缀和单调不减，一旦某个位置满足条件，后续所有位置都能组成多边形；而前缀和越大意味着选中的边越多、周长越长，因此最后一个满足条件的 i 对应的前缀和即为最大值。

四语言完整实现与关键细节

文档给出了 Python、Java、C++、Go 四种语言的实现，均可直接提交。下面逐一给出并补充要点说明。

Python3

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        ans = -1
        s = 0
        for x in nums:
            s += x
            if s > x * 2:  # s-x > x
                ans = s
        return ans

要点：s > x * 2 是 s - x > x 的等价写法，避免多余变量；ans 初始为 -1 表示无解。

Java

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        long ans = -1;
        long s = 0;
        for (int x : nums) {
            s += x;
            if (s > x * 2) { // s-x > x
                ans = s;
            }
        }
        return ans;
    }
}

要点：s 与 ans 必须用 long。因为 nums 中元素范围可达 10^9，若 n 较大，前缀和可能超过 int 上限（约 21 亿），导致溢出错误。

C++

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        ranges::sort(nums);
        long long ans = -1, s = 0;
        for (int x : nums) {
            s += x;
            if (s > x * 2) { // s-x > x
                ans = s;
            }
        }
        return ans;
    }
};

要点：使用 ranges::sort（C++20）简化排序代码；s 与 ans 使用 long long 防止溢出。

Go

func largestPerimeter(nums []int) int64 {
	slices.Sort(nums)
	ans := -1
	s := 0
	for _, x := range nums {
		s += x
		if s > x*2 { // s-x > x
			ans = s
		}
	}
	return int64(ans)
}

要点：Go 版本使用标准库 slices.Sort 完成升序排序；在 64 位平台上 Go 的 int 即为 64 位，s := 0 足够安全，最终以 int64 类型返回结果。该实现与仓库中 b.go 的源码完全一致。

复杂度分析

文档给出的复杂度结论为：

• 时间复杂度：O(n log n)，其中 n 为 nums 的长度，瓶颈在于排序。
• 空间复杂度：O(1)，不计入排序内部的栈开销（如快速排序的递归栈；原地排序本身不申请与 n 相关的额外数组）。

整个遍历只做一轮线性扫描，每次循环仅进行常数次加减与比较运算，因此排序之后的判定部分是 O(n)，整体由排序主导。

仓库源码级验证：实现、测试数据与测试框架

该题在当前仓库中有完整的工程化落地方案，可直接用于本地验证：

1. 函数实现

leetcode/biweekly/120/b/b.go 中的实现与文档的 Go 代码逐字一致，包名为 main，便于直接通过测试驱动运行。

2. 测试数据

leetcode/biweekly/120/b/b.txt 内置了 3 组样例，覆盖了有解、无解、边界情况：

[5,5,5]
15

[1,12,1,2,5,50,3]
12

[5,5,50]
-1

逐组分析：

• [5,5,5]：三条等边，5 + 5 > 5 成立，最大周长为 15；
• [1,12,1,2,5,50,3]：排序后为 [1,1,2,3,5,12,50]，前缀和分别判定，最终可组成边 1,1,2,3,5（和 12 > 5 不成立时舍去 12？），实际上最大满足条件的是选到 12 之前的位置，答案为 12；
• [5,5,50]：5 + 5 < 50，任何两条边都无法与 50 组成三角形，更无法组成多边形，返回 -1，对应无解分支。

3. 自动化测试入口

leetcode/biweekly/120/b/b_test.go 通过仓库自研测试框架 testutil.RunLeetCodeFuncWithFile 自动读取 b.txt 并跑测：

func Test_b(t *testing.T) {
	if err := testutil.RunLeetCodeFuncWithFile(t, largestPerimeter, "b.txt", 0); err != nil {
		t.Fatal(err)
	}
}

RunLeetCodeFuncWithFile 的实现在 leetcode/testutil/leetcode.go：它读取测试文件，按「函数入参个数 + 返回值个数」为一组切分输入输出，再调用 RunLeetCodeFuncWithExamples 逐组比对。参数 targetCaseNum 传 0 表示运行全部用例。本地运行方式为在 leetcode/biweekly/120/b/ 目录执行：

go test ./...

该测试文件头部注明由 copypasta/template/leetcode/generator_test.go 对应目录下的生成器自动生成，反映了仓库「每题一个 xxx.go + xxx.txt + xxx_test.go」的规范化刷题组织模式。

同类变体对比：从三角形到多边形

仓库中还收录了一道思路高度相关但更简单的经典题——力扣 976《三角形的最大周长》，位于 leetcode/weekly/119/b/b.go：

func largestPerimeter(nums []int) int {
	slices.Sort(nums)
	for i := len(nums) - 1; i >= 2; i-- {
		if nums[i-2]+nums[i-1] > nums[i] {
			return nums[i-2] + nums[i-1] + nums[i]
		}
	}
	return 0 // 无解
}

对比两者可以总结出清晰的套路：

对比维度	三角形最大周长（Weekly 119 B）	多边形最大周长（Biweekly 120 B）
边数限制	恰好 3 条	至少 3 条、尽可能多
判定条件	a + b > c（最大边 < 其余两边之和）	最大边 < 其余所有边之和
排序方向	从大到小枚举最大边，首次满足即返回	从小到大累积前缀和，最后一个满足位置的前缀和
无解返回值	0	-1

两道题共同揭示了「多边形判定」的统一原理：排序后，最大的边必须严格小于其余边之和。三角形是 n = 3 的特例，多边形推广到任意 n >= 3；三角形的"首次满足即返回"对应的是最长周长（因为三条边之和最大），而多边形的"最后一个满足"是因为前缀和单调递增。

小结与延伸思考

• 本题的核心考点是贪心 + 前缀和：排序保证「最长边」唯一可枚举；前缀和保证「其余边之和」可 O(1) 取得；「越大越好」的贪心选择使得结果天然是最大周长。
• 一个易错点是类型溢出：Java 必须用 long、C++ 必须用 long long，Go 依赖 64 位 int，Python 无此顾虑。
• 无解处理：多边形至少需要 3 条边，若不存在任何 s > x * 2 的位置，返回 -1。
• 该解法的时间复杂度 O(n log n) 对 n <= 10^5 级别的输入完全可行，空间 O(1) 也是题目的最优级别。

如果你正在研究贪心与思维类题目，仓库 README 末尾的分类题单（见 leetcode/biweekly/120/b/README.md）还列出了滑动窗口、二分、单调栈、网格图、位运算、图论、动态规划、数据结构、数学、字符串等十余类题单入口，可以作为继续系统刷题的路线图。