976-三角形的最大周长
大约 2 分钟
给定由一些正数(代表长度)组成的数组 nums ,返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形,返回 0。
示例 1:
输入:nums = [2,1,2]
输出:5
示例 2:
输入:nums = [1,2,1]
输出:0
提示:
3 <= nums.length <= 104
1 <= nums[i] <= 106
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/largest-perimeter-triangle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
组成三角形的三条边之间需要满足如下条件:
- 任意两边之和大于第三边
- 任意两边之差小于第三边
假设a b c为三边,则需要以下不等式均成立。
Math.abs(a - b) < c
Math.abs(a - c) < b
Math.abs(b - c) < a
a + b > c
a + c > b
b + c > a
我们考虑 a b c三者中最小值为a,最大值为c,中间值为b,以下六个不等式可以进行优化。
Math.abs(a - b) < c c为最大值,一定成立
Math.abs(a - c) < b 因为a < c,等价于 c - a > b
Math.abs(b - c) < a 因为b < c,等价于 c - b > a
a + b > c
a + c > b 一定成立
b + c > a 一定成立
根据上面的分析,我们可以将不等式简化为三条:
- c - a > b
- c - b > a
- a + b > c
我们发现,上面三条实际就是一条。
- a + b > c
所以,我们可以先将数组进行排序,然后判断出三个边中的最大值、最小值、中间值,满足上面不等式的 即为所求解。
public int largestPerimeter(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
//循环我们从最大值一侧开始,这样得到第一组符合条件的解后即为答案
for (int i = length - 1 ; i >= 0 ; i--) {
int max = nums[i];
for (int j = i-1; j >= 0 ; j--) {
int middle = nums[j];
for (int k = j-1; k >= 0 ; k--) {
int min = nums[k];
if (min + middle > max) {
return middle + max + min;
}
}
}
}
return 0;
}