找到最大周长的多边形

标签: 贪心 数组 前缀和 排序

难度: Medium

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

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

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

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

请你返回从 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 <= 105
  • 1 <= nums[i] <= 109

Submission

运行时间: 68 ms

内存: 29.9 MB

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        n = len(nums)
        s = sum(nums)
        nums.sort()
        for i in range(n - 1, 1, -1):
            if nums[i] * 2 < s:
                return s
            s -= nums[i]
        return -1

Explain

此题解的基本思路是首先对数组进行排序，然后从最大的元素开始，检查能否与前面的元素形成多边形。具体步骤包括：1. 计算数组的总和 `s`。2. 对数组进行排序。3. 从数组的最后一个元素开始向前遍历，检查当前元素是否小于前面所有元素的和（即是否可以与前面的元素形成多边形）。如果可以，则返回当前的总和 `s` 作为最大周长；如果不可以，就从总和中减去当前元素，继续检查前一个元素。4. 如果遍历完所有元素后都不能形成多边形，则返回 -1。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        n = len(nums)  # 获取输入数组的长度
        s = sum(nums)  # 计算数组元素的总和
        nums.sort()  # 对数组元素进行排序
        for i in range(n - 1, 1, -1):  # 从数组的最后一个元素向前遍历
            if nums[i] * 2 < s:  # 检查当前元素是否小于其余所有元素的和
                return s  # 如果条件满足，返回当前的总和作为最大周长
            s -= nums[i]  # 从总和中减去当前元素，继续检查前一个元素
        return -1  # 如果没有找到合适的组合，返回-1

Explore

排序是为了简化多边形的验证过程。通过将数组排序，可以确保在从数组的最大元素向前检查时，能够更方便地验证最大元素是否小于其余元素之和。这种方法有助于快速确定最大元素是否能与前面的元素组成多边形，而不需要对每个组合进行单独的验证。排序还有助于提高算法效率，因为一旦找到符合条件的组合，就可以立即停止搜索，而不需要继续检查更小的组合。

是的，这种方法确保了找到的多边形具有最大的周长。因为数组经过排序后，我们是从最大的元素开始向前查找，这样可以首先尝试将最大的元素包含在内。由于多边形的周长是边长的总和，包括尽可能大的边将有助于确保总和最大。一旦找到符合多边形条件的组合，由于是从最大值开始，所以这个组合的周长必定是最大可能的周长。

这个条件用于验证选定的最大边（nums[i]）是否小于其余所有边的总和。按照多边形的形成规则，任何一边的长度必须小于其他所有边长度的总和，以确保这些边可以闭合成一个多边形。在题解中，`s`代表当前考虑的所有边的总长度，`nums[i]`是当前考虑的最大边。如果`nums[i] * 2 < s`成立，意味着`nums[i]`小于其余边的总和，因此可以与它们形成一个闭合的多边形，从而满足多边形的基本形成条件。