daily_leetcode_2020_1129_976_三角形的最大周长

1 题目描述

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

如果不能形成任何面积不为零的三角形，返回 0

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

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

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

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

2 题解

最容易想到的方式是三层循环固定边取判断，这样的话复杂度显示高的没法说。

对于三条边a,b,c来说，组成三角形的条件是 $a+b>c , a-b<c$,假如是有序的话，那么就好判断多了，比如a,b,c经过降序排序后为b,a,c,那么只序判断$b<a+c$,因为a-c肯定是小于b的。

从上面来看排序的好处是简化了一个判断条件，更重要的是题目要求周长最大，周长最大，那么就要求三边在组成三角形的情况下尽量大，现在已经排好序了，那么挑最大的来判断就是。

贪心在这里贪的是什么？

固定一个最大的边，寻找两个比最大边尽量小的少的边，一起能够组成三角形的。

所以我们遍历相邻元素即可

为什么排序后，遍历相邻元素可行，有没有可能最优解为非相邻元素？

假如降序排序后的串为$a,b,c,d,e,f,g$, 那么我们就选非相邻的看看

第一步判断 a,b,c是否构成三角形($a<b+c$ ?)，假设不构成三角形

那么 我们现在有非相邻 a,c,d,相邻b,c,d两种选择，然而我们选择了b,c,d,为什么呢？

虽然a,c,d比b,c,d大，但是a,c,d并不构成三角形，因为a,b,c都够不成三角形,那么a,c,d更构不成三角形了($a<b+c$不成立,$c+d<b+c$ => $a<c+d$不成立)

class Solution:
    def largestPerimeter(self, A: List[int]) -> int:

        nums_len = len(A)
        if not A or nums_len < 3:
            return 0

        A.sort(reverse=True)
        for i in range(0, nums_len - 2):
            s = A[i + 1] + A[i + 2]
            if s > A[i]:
                return s + A[i]
        return 0

    def main(self):
        A = [3, 6, 2, 3]
        print(self.largestPerimeter(A))


if __name__ == '__main__':
    solution = Solution()
    solution.main()