Leetcode 976 Largest Perimeter Triangle

发表于 |

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
如果不能形成任何面积不为零的三角形，返回 0。

示例 1：
输入：[2,1,2]
输出：5

示例 2：
输入：[1,2,1]
输出：0

示例 3：
输入：[3,2,3,4]
输出：10

示例 4：
输入：[3,6,2,3]
输出：8

提示：

  1. 3 <= A.length <= 10000
  2. 1 <= A[i] <= 10^6

思路分析：
从最大的三个数开始找，只要能满足两边之和大于第三边即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def largestPerimeter(self, A):
        A.sort(reverse=True)
        i, j, k = 0, 1, 2
        while k<len(A) and A[i] >= A[j] + A[k]:
            i += 1
            j += 1
            k += 1
        if k < len(A):
            return A[i] + A[j] + A[k]
        return 0

# 84 / 84 test cases passed.
# diffculty: easy
# Runtime: 116 ms