class Solution {
public:
long long largestPerimeter(vector<int>& nums) {
}
};
100180. 找到最大周长的多边形
给你一个长度为 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 <= 1051 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 124 ms, 内存消耗: 8.7 MB, 提交时间: 2023-12-24 20:02:14
func largestPerimeter(nums []int) int64 {
slices.Sort(nums)
s := 0
for _, x := range nums {
s += x
}
for i := len(nums) - 1; i > 1; i-- {
x := nums[i]
if s > x*2 { // s-x > x
return int64(s)
}
s -= x
}
return -1
}
cpp 解法, 执行用时: 168 ms, 内存消耗: 77.2 MB, 提交时间: 2023-12-24 20:01:56
class Solution {
public:
long long largestPerimeter(vector<int> &nums) {
sort(nums.begin(), nums.end());
long long s = accumulate(nums.begin(), nums.end(), 0LL);
for (int i = nums.size() - 1; i > 1; --i) {
int x = nums[i];
if (s > x * 2) { // s-x > x
return s;
}
s -= x;
}
return -1;
}
};
java 解法, 执行用时: 32 ms, 内存消耗: 58.3 MB, 提交时间: 2023-12-24 20:01:43
class Solution {
public long largestPerimeter(int[] nums) {
Arrays.sort(nums);
long s = 0;
for (int x : nums) {
s += x;
}
for (int i = nums.length - 1; i > 1; i--) {
int x = nums[i];
if (s > x * 2) { // s-x > x
return s;
}
s -= x;
}
return -1;
}
}
python3 解法, 执行用时: 112 ms, 内存消耗: 30.5 MB, 提交时间: 2023-12-24 20:01:23
'''
把数组排序，枚举 nums[i] 作为最长的那条边，那么 nums[i] 左边的数之和越大越好，
这样才能尽可能地组成多边形，并且周长尽量长。
所以周长就是 nums 的某个前缀和。从大到小枚举 nums[i]，如果满足
nums[0]+nums[1]+⋯+nums[i−1]>nums[i]
那么答案就是
nums[0]+nums[1]+⋯+nums[i−1]+nums[i]
'''
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
nums.sort()
s = sum(nums)
for i in range(len(nums) - 1, 1, -1):
x = nums[i]
if s > x * 2: # s-x > x
return s
s -= x
return -1