【LeetCode每日一题】[简单]976. 三角形的最大周长

【LeetCode每日一题】[简单]976. 三角形的最大周长

976. 三角形的最大周长

976. 三角形的最大周长

算法思想：数组

题目：

java代码

O(nlogn)方法：

1. 将边按照从小到大顺序进行排序；
2. 从大到小进行搜索，如果，edge[i],edge[i+1],edge[i+2]能构成三角形，即为周长对大的三角形；

原因：
三角形条件： A<B+C （其中A是最长的边）；
要使得周长最长，B+C要尽可能的大；
排序后的B+C剩下边里面的最大，如果不满足，则没有边可以边满足B+C>A,即对A而言，不存在三角形；如果满足，则是最大周长的三角形；

class Solution {
    public int largestPerimeter(int[] A) {
		Arrays.sort(A);//排序(正序)
		int n = A.length;
		for (int i = n-1; i > 1; i--) {//从后向前,
			if (A[i] < A[i-1] + A[i-2]) {//成立,存在三角形
				return A[i] + A[i-1] + A[i-2];
			}
		}
		return 0;
    }
}