给定由一些正数 (代表长度) 组成的数组 A, 返回由其中三个长度组成的, 面积不为零的三角形的最大周长.
如果不能形成任何面积不为零的三角形, 返回 0.
示例 1:
输入:[2,1,2]
输出: 5
示例 2:
输入:[1,2,1]
输出: 0
示例 3:
输入:[3,2,3,4]
输出: 10
示例 4:
输入:[3,6,2,3]
输出: 8
提示:
- 3 <= A.length <= 10000
- 1 <= A[i] <= 10^6
思路
不失一般性的, 我们假设三角形的边长满足 a \leq b \leq ca≤b≤c. 那么这三条边组成三角形的面积非零的充分必要条件是 a + b> ca+b>c.
再假设我们已经知道 cc 的长度了, 我们没有理由不从数组中选择尽可能大的 aa 与 bb. 因为当且仅当 a + b> ca+b>c 的时候, 它们才能组成一个三角形.
算法
基于这种想法, 一个简单的算法就呼之欲出: 排序数组. 对于数组内任意的 cc, 我们选择满足条件的最大的 a \leq b \leq ca≤b≤c, 也就是大到小排序, 位于 cc 后面的两个元素. 从大到小枚举 cc, 如果能组成三角形的话, 我们就返回答案.
- int largestPerimeter(vector<int>& A){
- sort(A.begin(),A.end());
- for(int i = A.size()-3;i>=0;i--){
- if(A[i]+A[i+1]>A[i+2])
- return A[i]+A[i+1]+A[i+2];
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2930467.html