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
解释：从 nums 中可以构成的具有最大周长的多边形有 5 条边：1, 1, 2, 3 和 5。周长为 1 + 1 + 2 + 3 + 5 = 12。
我们无法构成一个以 12 或 50 为最长边的多边形，因为其他边的长度之和没有超过它们中的任何一个。
可以证明最大可能的周长为 12。

示例 3：

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

提示：

  • 3 <= n <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这是一道经典的贪心算法题目。题目的核心在于理解多边形的构成条件：最长边必须小于其他所有边的长度之和。

解题思路

核心观察： 为了构造周长最大的多边形，我们应该尽可能多地使用数组中的边。

  1. 排序：首先对数组进行排序，这样可以方便地处理边长关系
  2. 贪心策略：从小到大尝试每条边作为最长边的情况
  3. 前缀和优化：使用前缀和快速计算前面所有边的长度之和
  4. 多边形条件检查：对于每个可能的最长边，检查前面所有边的和是否大于这条边

算法流程：

  1. 对数组排序
  2. 计算前缀和数组
  3. 从后往前遍历，对每个位置 i，检查前缀和[i-1] 是否大于 nums[i]
  4. 如果满足条件且至少有3条边，更新最大周长
  5. 返回结果

时间复杂度： O(n log n)，主要来自排序 空间复杂度： O(1)，只使用常数额外空间

这种方法的正确性在于：如果选择某条边作为最长边，那么包含所有更小的边总是最优的，因为这样能获得最大的周长。

代码实现

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        long long sum = 0;
        long long maxPerimeter = -1;
        
        for (int i = 0; i < nums.size(); i++) {
            if (i >= 2 && sum > nums[i]) {
                maxPerimeter = sum + nums[i];
            }
            sum += nums[i];
        }
        
        return maxPerimeter;
    }
};

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        
        prefix_sum = 0
        max_perimeter = -1
        
        for i in range(len(nums)):
            if i >= 2 and prefix_sum > nums[i]:
                max_perimeter = prefix_sum + nums[i]
            prefix_sum += nums[i]
        
        return max_perimeter

public class Solution {
    public long LargestPerimeter(int[] nums) {
        Array.Sort(nums);
        
        long prefixSum = 0;
        long maxPerimeter = -1;
        
        for (int i = 0; i < nums.Length; i++) {
            if (i >= 2 && prefixSum > nums[i]) {
                maxPerimeter = prefixSum + nums[i];
            }
            prefixSum += nums[i];
        }
        
        return maxPerimeter;
    }
}

var largestPerimeter = function(nums) {
    nums.sort((a, b) => a - b);
    
    let prefixSum = 0;
    let maxPerimeter = -1;
    
    for (let i = 0; i < nums.length; i++) {
        if (i >= 2 && prefixSum > nums[i]) {
            maxPerimeter = prefixSum + nums[i];
        }
        prefixSum += nums[i];
    }
    
    return maxPerimeter;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要来自排序操作，遍历数组为O(n)
空间复杂度O(1)只使用常数额外空间存储前缀和和结果

相关题目