啪一下很快哈!!贪心+排序?这么简单,我大意了?一跑AC了那没事了
题目描述
给定由一些正数(代表长度)组成的数组 A,返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形,返回 0。
样例
算法1
(贪心+排序)
数学知识:两边之和大于第三边可以构成一个三角形。
思路:
那么将整个数组从小到大排序,每次贪心的取。
取最大的后三个值来试着构成三角形,如果可以构成三角形,返回周长。
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int largestPerimeter(vector<int>& A) {
sort(A.begin(), A.end());
//这里注意下边界是大于等于2
for (int i = A.size()-1; i >=2; i--){
int a = A[i], b = A[i-1], c = A[i-2];
if (b + c>a) return a + b + c;
}
return 0;
}
};