题目描述

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

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

样例

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

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

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

输入：[3,6,2,3]
输出：8

注意

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

算法

(排序，贪心) $O(n \log n)$

1. 将所有边按长度从大到小排序。下边证明如果存在可行的三角形，则周长最大的三角形的三条边在数组中一定是相邻的。假设三条边的长度分别为 x, y 和 z，则构成三角形充要条件为 x + y > z 且 abs(x - y) < z。
2. 如果选出的三条边在数组中不相邻，假设我们选出了 x, y’ 和 z’ 构成三角形，则存在 x < y < y'，仍然满足三角形的条件，但周长会更大。
3. 所以我们只需要枚举在数组中相邻的三条边即可。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，枚举遍历的时间复杂度为 $O(n)$，故总时间复杂度为 $O(n \log n)$。

空闲复杂度

• 仅需要常数的额外空间，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        int n = A.size();
        sort(A.begin(), A.end(), greater<>());

        for (int i = 0; i < n - 2; i++) {
            int x = A[i], y = A[i + 1], z = A[i + 2];
            if (x + y > z && x - y < z)
                return x + y + z;
        }

        return 0;
    }
};