跳至主要內容

976-三角形的最大周长

daipeng大约 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;
    }