LeetCode 2971 详解Find Polygon With the Largest Perimeter——排序、前缀和与最大堆三种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 2971「Find Polygon With the Largest Perimeter」展开以本仓库 articles/find-polygon-with-the-largest-perimeter.md 为骨架结合仓库内 Python、Java、Kotlin 等多语言实现系统讲解「多边形不等式 前缀和 排序」的核心思路并给出暴力枚举、排序扫描、最大堆三种递进解法及其多语言代码。读完你将掌握如何把能否构成多边形的判定问题转化为一次有序扫描的贪心问题并理解大数溢出、严格不等式等关键细节。1. 前置知识在动手解题之前需要先具备三个基础能力它们是本题三种解法的共同根基排序Sorting将数组升序排列后可以高效定位最长边并让其余边自然聚拢在最长边之前从而把比较转化为顺序扫描。前缀和Prefix Sum维护一个运行中的累加和total可以 O(1) 时间拿到所有比当前元素小的边之和避免重复求和。多边形不等式Polygon Inequality一个由若干条边组成的多边形合法当且仅当最长边严格小于其余所有边之和。这是贯穿全题唯一的判定条件。2. 问题本质题目给一个正整数数组nums要求从中选出若干条边使其能构成一个多边形并且周长所有选中边长之和最大若不存在任何合法多边形则返回-1。关键观察若一组边能构成多边形那么把这组边里最大的那条边与其余边分开看判定条件就是最长边 其余边之和而周长最大意味着如果某个前缀排序后已经合法那么继续向后扩展前缀只会让周长更大因为新增的都是正数边。这为解法 2 的持续更新答案、取最后一次合法结果提供了理论基础。3. 解法一暴力枚举Brute Force3.1 直觉不排序直接尝试把数组中的每一个元素当作潜在的最长边。对每个候选最长边累加所有小于等于它且不是它自己的其他元素若该累加和大于候选边就构成一个合法多边形记录其周长并更新最大值。3.2 算法步骤初始化res -1用于记录找到的最大周长。遍历nums将每个nums[i]视为潜在最长边。对每个i累加所有满足nums[j] nums[i]且j ! i的元素得到cur。若cur nums[i]其余边之和严格大于最长边更新res max(res, cur nums[i])。全部检查完毕后返回res。3.3 多语言实现class Solution: def largestPerimeter(self, nums: List[int]) - int: n len(nums) res -1 for i, large in enumerate(nums): cur 0 for j, side in enumerate(nums): if i ! j and side large: cur side if cur large: res max(res, cur large) return respublic class Solution { public long largestPerimeter(int[] nums) { int n nums.length; long res -1; for (int i 0; i n; i) { int large nums[i]; long cur 0; for (int j 0; j n; j) { if (i ! j nums[j] large) { cur nums[j]; } } if (cur large) { res Math.max(res, cur large); } } return res; } }class Solution { public: long long largestPerimeter(vectorint nums) { int n nums.size(); long long res -1; for (int i 0; i n; i) { long long large nums[i]; long long cur 0; for (int j 0; j n; j) { if (i ! j nums[j] large) { cur nums[j]; } } if (cur large) { res max(res, cur large); } } return res; } };class Solution { /** * param {number[]} nums * return {number} */ largestPerimeter(nums) { const n nums.length; let res -1; for (let i 0; i n; i) { const large nums[i]; let cur 0; for (let j 0; j n; j) { if (i ! j nums[j] large) { cur nums[j]; } } if (cur large) { res Math.max(res, cur large); } } return res; } }func largestPerimeter(nums []int) int64 { n : len(nums) var res int64 -1 for i : 0; i n; i { large : nums[i] var cur int64 0 for j : 0; j n; j { if i ! j nums[j] large { cur int64(nums[j]) } } if cur int64(large) { if curint64(large) res { res cur int64(large) } } } return res }impl Solution { pub fn largest_perimeter(nums: Veci32) - i64 { let n nums.len(); let mut res: i64 -1; for i in 0..n { let large nums[i] as i64; let mut cur: i64 0; for j in 0..n { if i ! j nums[j] as i64 large { cur nums[j] as i64; } } if cur large { res res.max(cur large); } } res } }3.4 复杂度分析时间复杂度O(n²)每个元素都要对全数组求和一次。空间复杂度O(1)额外空间。实现细节提示注意cur与res在 Java/C/Go/Rust 等强类型语言中必须使用 64 位整数long/long long/int64/i64原因见后文常见陷阱。4. 解法二排序 前缀和扫描Sorting——推荐解法4.1 直觉对数组升序排序后遍历到任意元素num时它之前的所有元素都小于等于它。于是其余边之和就是此前所有元素的运行累加和total。判定条件退化为一行total num ⟺ 存在以 num 为最长边的合法多边形由于我们希望周长最大而数组已按升序排列最后一个满足条件的位置所对应的周长就是全局最大周长——这正是仓库中 Python 实现 注释Time complexity O(nlogn)所对应的标准解法。4.2 算法步骤将数组升序排序。初始化res -1、total 0前缀和。依次遍历每个num若total num说明以num为最长边可以构成多边形更新res total num当前前缀全部边 最长边即周长。将num累加进total。返回res。注意循环顺序先判断、后累加。这样total恰好代表除当前元素以外的所有已扫描边之和。4.3 多语言实现class Solution: def largestPerimeter(self, nums: List[int]) - int: nums.sort() res -1 total 0 for num in nums: if total num: res total num total num return respublic class Solution { public long largestPerimeter(int[] nums) { Arrays.sort(nums); long res -1; long total 0; for (int num : nums) { if (total num) { res total num; } total num; } return res; } }class Solution { public: long long largestPerimeter(vectorint nums) { sort(nums.begin(), nums.end()); long long res -1; long long total 0; for (int num : nums) { if (total num) { res total num; } total num; } return res; } };class Solution { /** * param {number[]} nums * return {number} */ largestPerimeter(nums) { nums.sort((a, b) a - b); let res -1; let total 0; for (let num of nums) { if (total num) { res total num; } total num; } return res; } }func largestPerimeter(nums []int) int64 { sort.Ints(nums) var res int64 -1 var total int64 0 for _, num : range nums { if total int64(num) { res total int64(num) } total int64(num) } return res }class Solution { fun largestPerimeter(nums: IntArray): Long { nums.sort() var res: Long -1 var total: Long 0 for (num in nums) { if (total num) { res total num } total num } return res } }impl Solution { pub fn largest_perimeter(mut nums: Veci32) - i64 { nums.sort(); let mut res: i64 -1; let mut total: i64 0; for num in nums { if total num as i64 { res total num as i64; } total num as i64; } res } }4.4 仓库源码印证本仓库的 Java 实现 与上述思路完全一致且刻意把累加变量命名为amt、循环变量命名为i逻辑上等价public class Solution { public long largestPerimeter(int[] nums) { Arrays.sort(nums); long res -1, amt 0; for (int i : nums) { if (amt i) res amt i; amt i; } return res; } }Kotlin 实现 则额外提供了一种**自顶向下top-down**的同思路变体先算全数组总和sum再按降序遍历逐个从sum中扣除当前最大边n若剩余部分rest sum - n n则直接返回sum——因为降序扫描中第一个满足条件的组合就是周长最大的组合。这种写法与排序解法在数学上等价但代码视角相反值得对比阅读。4.5 复杂度分析时间复杂度O(n log n)主要来自排序。空间复杂度O(1)或O(n)取决于具体语言排序算法的实现如原地快速排序为 O(log n) 栈空间归并排序为 O(n)。5. 解法三最大堆Max Heap5.1 直觉不排序改用最大堆从大到小处理元素。先求出全数组总和total反复取出当前最大元素largest若从total中扣除largest后剩余和仍大于largest说明其余所有边之和 最长边此时total largest即整组边就是能构成的最大周长直接返回。否则把largest从总和里永久剔除继续尝试次大元素。该方法在实践中常常提前命中答案无需处理完所有元素因此可能比排序更快。5.2 算法步骤将所有元素放入最大堆并计算总和total。当堆中元素数量大于2时循环取出最大元素largest从total中减去largest若largest total返回total largest作为周长。循环结束仍未找到返回-1。循环条件size 2保证至少还有 3 条边最长边 至少两条其余边这是多边形合法性的下限详见常见陷阱。5.3 多语言实现class Solution: def largestPerimeter(self, nums: List[int]) - int: nums [-num for num in nums] heapq.heapify(nums) total -sum(nums) while len(nums) 2: largest -heapq.heappop(nums) total - largest if largest total: return total largest return -1public class Solution { public long largestPerimeter(int[] nums) { PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a); long total 0; for (int num : nums) { maxHeap.add(num); total num; } while (maxHeap.size() 2) { int largest maxHeap.poll(); total - largest; if (largest total) { return total largest; } } return -1; } }class Solution { public: long long largestPerimeter(vectorint nums) { priority_queueint maxHeap(nums.begin(), nums.end()); long long total accumulate(nums.begin(), nums.end(), 0LL); while (maxHeap.size() 2) { int largest maxHeap.top(); maxHeap.pop(); total - largest; if (largest total) { return total largest; } } return -1; } };class Solution { /** * param {number[]} nums * return {number} */ largestPerimeter(nums) { const maxHeap new MaxPriorityQueue(); let total 0; nums.forEach((num) { total num; maxHeap.enqueue(num); }); while (maxHeap.size() 2) { const largest maxHeap.dequeue().element; total - largest; if (largest total) return total largest; } return -1; } }func largestPerimeter(nums []int) int64 { h : MaxHeap{} heap.Init(h) var total int64 0 for _, num : range nums { heap.Push(h, num) total int64(num) } for h.Len() 2 { largest : heap.Pop(h).(int) total - int64(largest) if int64(largest) total { return total int64(largest) } } return -1 } type MaxHeap []int func (h MaxHeap) Len() int { return len(h) } func (h MaxHeap) Less(i, j int) bool { return h[i] h[j] } func (h MaxHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MaxHeap) Push(x any) { *h append(*h, x.(int)) } func (h *MaxHeap) Pop() any { old : *h n : len(old) x : old[n-1] *h old[0 : n-1] return x }class Solution { fun largestPerimeter(nums: IntArray): Long { val maxHeap PriorityQueueInt(compareByDescending { it }) var total: Long 0 for (num in nums) { maxHeap.add(num) total num } while (maxHeap.size 2) { val largest maxHeap.poll() total - largest if (largest total) { return total largest } } return -1 } }impl Solution { pub fn largest_perimeter(nums: Veci32) - i64 { let mut max_heap BinaryHeap::new(); let mut total: i64 0; for num in nums { max_heap.push(num); total num as i64; } while max_heap.len() 2 { let largest max_heap.pop().unwrap() as i64; total - largest; if largest total { return total largest; } } -1 } }5.4 仓库源码中的总和两倍等价写法仓库的 Python 实现 第二版把最大堆思路写成更紧凑的形式并标注Time complexity O(n 30logn) ~ O(n)class Solution: def largestPerimeter(self, nums: List[int]) - int: curSum sum(nums) heapq._heapify_max(nums) while nums and curSum nums[0] * 2: curSum - heapq._heappop_max(nums) return curSum if len(nums) 2 else -1这里的判定条件curSum nums[0] * 2是largest total_rest的代数等价变形因为curSum largest total_rest所以total_rest largest ⟺ curSum - largest largest ⟺ curSum 2 * largest ⟺ curSum nums[0] * 2。循环不断弹出最大元素直到不等式满足最后若剩余边数大于 2curSum就是答案。同样的变形也出现在 Kotlin 实现 第三版的while (max.isNotEmpty() sum max.peek() * 2)中。5.5 复杂度分析时间复杂度Python / C / JavaScriptO(n (30·log n))。堆化heapify为 O(n)而单次最多弹出约 30 次因元素最大 10⁹最多约 30 个元素参与判定即可收敛故近似O(n)JavaPriorityQueue 逐个插入为O(n log n)。空间复杂度O(n)堆需要存储全部元素。6. 常见陷阱Common Pitfalls6.1 误用而非严格大于多边形不等式要求最长边严格小于其余边之和等价于其余边之和严格大于最长边。若把误写成会把退化多边形——即各边共线、恰好被最长边拉直的情况——错误地判为合法。例如nums [1, 1, 2]1 1 2并不大于 2三条线段只能拼成一条直线不能构成三角形应返回-1若用则会错误地返回周长4。6.2 大数求和溢出题目约束数组长度可达 10⁵、单个元素可达 10⁹全数组之和最大可到 10¹⁴远超 32 位整数范围。因此累加和与最终结果必须使用 64 位整数Java 用long、C 用long long、Go 用int64、Rust 用i64否则会溢出导致比较错误。本仓库所有语言实现均严格遵循这一点例如 Java 解法中res、amt都声明为long。6.3 忽略多边形至少需要 3 条边合法多边形至少需要 3 条边。在排序解法中遍历到第 0、1 个元素时此前分别只有 0、1 个元素total根本不可能满足至少两条其余边的约束虽然排序解法中total num在元素个数不足时天然不成立但若提前在索引 0 或 1 处强行校验或像最大堆解法那样把循环边界设成size 2之外的数值就可能得到错误结果或越界访问。最大堆解法中while (size 2)正是对这一约束的显式保证。7. 三种解法对比总结解法核心思想时间复杂度空间复杂度适用场景暴力枚举每个元素作最长边全量求和O(n²)O(1)理解题意、小规模输入排序 前缀和升序扫描运行和即其余边之和O(n log n)O(1) / O(n)面试首选简洁且稳定最大堆从最大边往下试提前返回O(n) 或 O(n log n)O(n)追求平均性能更优的实现三种思路共享同一条数学核心——多边形不等式。掌握先排序、再以前缀和维护其余边之和的范式后还可以把它迁移到其他以最大元素为锚点做判定的题目中。若想深入更多类似思路可继续阅读本仓库的 articles 目录 中关于排序与前缀和的系列题解或在 README.md 中定位本仓库的完整题目索引。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考