题目地址：https://leetcode.com/problems/largest-perimeter-triangle/
题目描述
Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.
Ifit is impossible to form any triangle of non-zero area, return 0.
Example 1:
Input: [2,1,2]
Output: 5
Example 2:
Input: [1,2,1]
Output: 0
Example 3:
Input: [3,2,3,4]
Output: 10
Example 4:
Input: [3,6,2,3]
Output: 8
Note:
1、 3<=A.length<=10000；
2、 1<=A[i]<=10^6；
题目大意
从一个数组中选择3条边构成三角形，求该三角形最大的周长。
解题方法
排序
首先，我们肯定需要排序的，这个不解释。
假设排序完成之后的数组为[a, b, c, d, e, f]，其中a <= b <= c <= d <= e <= f.为了尽可能构成周长最大的三角形，我们从右向左进行遍历。只需要对连续的三条边进行判断即可找出周长最大的三角形。理由如下。
抽出三条边，假设为d,e,f，那么这三条边组成三角形的充分条件是d + e > f。下面进行证明：
对于任意三条边，能组成三角形的充分条件是两边之和大于第三边，两边之差小于第三边。由于d <= e <= f，显然有e + f > d，d + f > e。又d + e > f，则满足任意两边之和大于第三边。由于d <= e <= f，则e - d < f。又d + e > f，则f - e < d, f - d < e，则满足任意两边只差小于第三边。所以，当d + e > f时能够成三角形。
下面证明选取的次大边和最大边必须相邻，即如果最大边选择f，则次大边必须选择e。由d + e > f知， 最大边 - 次大边 < 最小边。当我们次大边选择e时，假如最小边无论如何选择不能构成三角形，即target = f - e > d。那么，次大边选择更小的数字时，target会更大，仍然有target = f - d > f - e > d > c。总之，如果当次大边选择和最大边相邻时，如果不能构成三角形，则次大边和最大边不相邻，更不能构成三角形。
再下面证明，最小边必须和次大边必须相邻，即如果最大边选择f、次大边选择e时，最小边必须选择d。这个很好证明，由于d + e > f，即target = f - e < 最小边，我们肯定只能在满足该条件的边中选择最大的，才能使得构成三角形的周长最大。而数组是已经排了序的，所以，最小边选择d时，要么不能构成三角形，要么就构成在最大边和次大边为f,e时周长最大的三角形。
综上，在排序了的数组中选择三条边构成最大周长的三角形的充分条件是，三条边必须连续选择，且尽可能选择最大的边。
python代码如下：
class Solution(object):
def largestPerimeter(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
N = len(A)
res = 0
A[i - 2], A[i - 1], A[i]
for i in range(N - 1, 1, -1):
if A[i - 2] + A[i - 1] > A[i]:
return A[i - 2] + A[i - 1] + A[i]
return 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发