Leetcode-977-有序数组的平方

Leetcode-976-三角形的最大周长

题目描述

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

输入：[2,1,2]
输出：5

示例 2：

输入：[1,2,1]
输出：0

示例 3：

输入：[3,2,3,4]
输出：10

示例 4：

输入：[3,6,2,3]
输出：8

思路 ： 数学

1. 为什么只需要判断 a + b > c ?

正常情况下，对于三条边长，判断能否组成三角形需要判断任何两条边长相加都大于其余的一条边长，即：

a + b > c && a + c > b && b + c > a

而如果已知a<=b<=c，那么必然有：

1. a + c > b，因为c >= b，那c加上一个正数一定就比b大了。而题目里说所数都>=1，所以c加上a一定比b大。
2. b + c > a，因为b和c至少跟a一样大(b>=a, c>=a)，加起来的结果至少有2a，即 b+c >= 2a > a所以最终只需要判断a + b > c即可。

2. 为什么只需要判断数组中相邻的三个数？

在固定最后一个数 A[i] 时，前两个数需不需要再往前找呢？

如果 A[i-2] + A[i-1] <= A[i] ，这三个数一定不能构成三角形，而A[i-3]以及更往前的数，都小于等于A[i-2]，所以再往前取任何两个数只会让相加的值更小，就更不能满足 A[j] + A[k] > A[i]了 (j<i-2, k<i-1, j<k)。所以如果相邻的数构不成三角形，就不需要再固定第三个数并往前找两个数了。

如果 A[i-2] + A[i-1] > A[i]，这三个数可以构成三角形，再往前找只会让周长变短，所以也不用再往前了。

class Solution {
    public int largestPerimeter(int[] A) {
        // 1. 对数组进行排序
        Arrays.sort(A);

        // 2. a + b > c 假定 a <= b <= c
        for(int  i = A.length - 1;i >= 2;i--){
            if(A[i - 2] + A[i - 1] > A[i]){
                return A[i - 2] + A[i - 1] + A[i];
            }
        }

        return 0;
    }
}

复杂度分析

• 时间复杂度 ： O(nlogn)

• 空间复杂度： O (logn)

打赏