给定由一些正数(代表长度)组成的数组 A,返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形,返回 0
解题思路
三条边组成面积不为零的三角形的充分必要条件为 a + b > c,因此我们首先将数组升序排序,从最后三个开始枚举,找出符合构成三角形的最大的三个数即可
class Solution {
public int largestPerimeter(int[] A) {
Arrays.sort(A);
int a = A.length - 3, b = A.length - 2, c = A.length - 1;
while(a >= 0) {
if(A[a] + A[b] > A[c]) {
return A[a] + A[b] + A[c];
}
a--;
b--;
c--;
}
return 0;
}
}
时间复杂度:O(NlogN),其中 N 是数组 A 的长度
空间复杂度:O(logN)
|