找到最大周长的多边形

You are given an array of positive integers nums of length n.

A polygon is a closed plane figure that has at least 3 sides. The longest side of a polygon is smaller than the sum of its other sides.

Conversely, if you have k (k >= 3) positive real numbers a1, a2, a3, ..., ak where a1 <= a2 <= a3 <= ... <= ak and a1 + a2 + a3 + ... + ak-1 > ak, then there always exists a polygon with k sides whose lengths are a1, a2, a3, ..., ak.

The perimeter of a polygon is the sum of lengths of its sides.

Return the largest possible perimeter of a polygon whose sides can be formed from nums, or -1 if it is not possible to create a polygon.

 

Example 1:

Input: nums = [5,5,5]
Output: 15
Explanation: The only possible polygon that can be made from nums has 3 sides: 5, 5, and 5. The perimeter is 5 + 5 + 5 = 15.

Example 2:

Input: nums = [1,12,1,2,5,50,3]
Output: 12
Explanation: The polygon with the largest perimeter which can be made from nums has 5 sides: 1, 1, 2, 3, and 5. The perimeter is 1 + 1 + 2 + 3 + 5 = 12.
We cannot have a polygon with either 12 or 50 as the longest side because it is not possible to include 2 or more smaller sides that have a greater sum than either of them.
It can be shown that the largest possible perimeter is 12.

Example 3:

Input: nums = [5,5,50]
Output: -1
Explanation: There is no possible way to form a polygon from nums, as a polygon has at least 3 sides and 50 > 5 + 5.

 

Constraints:

• 3 <= n <= 105
• 1 <= nums[i] <= 109

/*
题目思路：
1. 对数组进行排序。
2. 从最大的元素开始，检查前两个元素之和是否大于当前元素。
3. 如果条件满足，返回三个元素的和。
4. 如果不满足，继续向前检查。
5. 如果遍历完数组，找不到满足条件的三条边，返回-1。
*/
import java.util.Arrays;
public class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums); // Step 1: 对数组进行排序
        return IntStream.range(2, nums.length) // Step 2: 从最大的元素开始
                        .map(i -> nums.length - 1 - i)
                        .filter(i -> nums[i] < nums[i + 1] + nums[i + 2]) // Step 3: 检查前两个元素之和是否大于当前元素
                        .map(i -> nums[i] + nums[i + 1] + nums[i + 2]) // Step 4: 条件满足，返回三个元素的和
                        .findFirst()
                        .orElse(-1); // Step 5: 遍历完数组，找不到满足条件的三条边，返回-1
    }
}

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

O(n log n)

O(1)