What is the main idea behind Find Polygon With the Largest Perimeter?

The key is to sort the array and use a greedy approach to select the largest valid triplet that satisfies the polygon inequality.

Why do we need to sort the array first?

Sorting ensures that the largest sides are considered first, which guarantees that the first valid polygon found will have the maximum perimeter.

What if no valid polygon can be formed?

Return -1, as this indicates that all triplets fail the polygon inequality with the longest side exceeding the sum of the others.

Can this method handle very large arrays?

Yes, sorting and iterating through the array scales with O(N\cdot logN), which is efficient for arrays up to 10^5 elements.

How does the greedy choice plus invariant validation pattern apply here?

By always picking the largest available sides and validating the polygon inequality, you ensure both optimal perimeter and correctness, directly applying the pattern.

#2971

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

找到最大周长的多边形

给你一个长度为 n 的正整数数组 nums 。多边形指的是一个至少有 3 条边的封闭二维图形。多边形的最长边一定小于所有其他边长度之和。如果你有 k （ k >= 3 ）个正数 a 1 ， a 2 ， a 3 , ...， a k 满足 a 1 2 3 k 且 a 1 + a …

数组贪心排序前缀和

题目描述

给你一个长度为 n 的正整数数组 nums 。

多边形 指的是一个至少有 3 条边的封闭二维图形。多边形的 最长边 一定小于所有其他边长度之和。

如果你有 k （k >= 3）个正数 a₁，a₂，a₃, ...，a_k 满足 a₁ <= a₂ <= a₃ <= ... <= a_k 且 a₁ + a₂ + a₃ + ... + a_k-1 > a_k，那么一定存在一个 k 条边的多边形，每条边的长度分别为 a₁ ，a₂ ，a₃ ， ...，a_k 。

一个多边形的周长指的是它所有边之和。

请你返回从 nums 中可以构造的 多边形 的 最大周长 。如果不能构造出任何多边形，请你返回 -1 。

示例 1：

输入：nums = [5,5,5]
输出：15
解释：nums 中唯一可以构造的多边形为三角形，每条边的长度分别为 5 ，5 和 5 ，周长为 5 + 5 + 5 = 15 。

示例 2：

输入：nums = [1,12,1,2,5,50,3]
输出：12
解释：最大周长多边形为五边形，每条边的长度分别为 1 ，1 ，2 ，3 和 5 ，周长为 1 + 1 + 2 + 3 + 5 = 12 。
我们无法构造一个包含变长为 12 或者 50 的多边形，因为其他边之和没法大于两者中的任何一个。
所以最大周长为 12 。

示例 3：

输入：nums = [5,5,50]
输出：-1
解释：无法构造任何多边形，因为多边形至少要有 3 条边且 50 > 5 + 5 。

提示：

3 <= n <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：排序 + 前缀和

我们可以将数组 $nums$ 排序，然后定义一个答案变量 $ans$ ，初始值为 $-1$ 。

接下来，我们在 $[3, n]$ 的范围内枚举最长边 $a_k$ ，如果 $a_1 + a_2 + \cdots + a_{k-1} > a_k$ ，那么就可以构成一个周长为 $a_1 + a_2 + \cdots + a_k$ 的多边形。这里，我们可以使用前缀和数组 $s$ ，其中 $s_i = a_1 + a_2 + \cdots + a_i$ ，那么 $a_1 + a_2 + \cdots + a_{k-1} = s_{k-1}$ ，判断是否 $s_{k-1} > a_k$ ，如果是，那么更新答案 $ans = \max(ans, s_k)$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        s = list(accumulate(nums, initial=0))
        ans = -1
        for k in range(3, len(nums) + 1):
            if s[k - 1] > nums[k - 1]:
                ans = max(ans, s[k])
        return ans

speed

复杂度分析

指标	值
时间	O(N\cdot logN)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Sorting the array suggests a greedy approach for largest perimeter selection.
question_mark
Examining triplets indicates knowledge of polygon inequalities.
question_mark
Returning immediately on first valid triplet shows understanding of optimal greedy invariant.

warning

常见陷阱

外企场景

error
Failing to sort the array may lead to suboptimal perimeter calculation.
error
Not validating the polygon inequality for the triplet can produce invalid polygons.
error
Assuming any three sides form a polygon without checking the longest side.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the polygon with the smallest perimeter instead of the largest, requiring reversed greedy logic.
arrow_right_alt
Determine the number of distinct valid polygons that can be formed from nums.
arrow_right_alt
Compute the largest perimeter for polygons with more than three sides, generalizing triplet checks.

help

常见问题

外企场景

继续练习

#2587 重排数组以得到最大前缀分数 #3362 零数组变换 III #3413 收集连续 K 个袋子可以获得的最多硬币数量