2971. 找到最大周长的多边形

题目描述

给你一个长度为 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⁹

解法

方法一：排序 + 前缀和

思考

多边形条件是最长边小于其余边之和。排序后最长边若取 \(a_k\)，其余边应取更小的 \(k-1\) 条才能尽量构成且周长更大，故只需检查前 \(k\) 项。

前缀和 \(s[k-1]>nums[k-1]\) 则更新周长 \(s[k]\)。从 \(k=3\) 扫到 \(n\)，\(n \le 10^5\)。

我们可以将数组 \(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\) 的长度。

Python3JavaC++GoTypeScript

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

class Solution {
    public long largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long[] s = new long[n + 1];
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + nums[i - 1];
        }
        long ans = -1;
        for (int k = 3; k <= n; ++k) {
            if (s[k - 1] > nums[k - 1]) {
                ans = Math.max(ans, s[k]);
            }
        }
        return ans;
    }
}

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<long long> s(n + 1);
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + nums[i - 1];
        }
        long long ans = -1;
        for (int k = 3; k <= n; ++k) {
            if (s[k - 1] > nums[k - 1]) {
                ans = max(ans, s[k]);
            }
        }
        return ans;
    }
};

func largestPerimeter(nums []int) int64 {
    sort.Ints(nums)
    n := len(nums)
    s := make([]int, n+1)
    for i, x := range nums {
        s[i+1] = s[i] + x
    }
    ans := -1
    for k := 3; k <= n; k++ {
        if s[k-1] > nums[k-1] {
            ans = max(ans, s[k])
        }
    }
    return int64(ans)
}

function largestPerimeter(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + nums[i];
    }
    let ans = -1;
    for (let k = 3; k <= n; ++k) {
        if (s[k - 1] > nums[k - 1]) {
            ans = Math.max(ans, s[k]);
        }
    }
    return ans;
}

2971. 找到最大周长的多边形

题目描述

解法

方法一：排序 + 前缀和

评论