[LeetCode] 976. Largest Perimeter Triangle

[grandyang]

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it 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

这道题给了个正整数数组，让从中选三个数当作三角形的三条边，问能组成的三角形的最大周长是多少。因为要组成三角形，所以必须要满足两边之和大于第三边这一条性质，我们并不用去检测所有的组合情况，而是只要判断较短的两边之和是否大于最长的那条边就可以了。虽然这道是 Easy 题目，但是 OJ 仍然不让用暴力搜索法，遍历任意三条边是会超时的。所以只能想优化的解法，既然要周长最长，则肯定是选较大的数字先测比较好。这里就先给数组排个序，然后从末尾开始，每次取出三个数字，先检测能否组成三角形，可以的话直接返回周长，不行的话就继续往前取，若都不行的话，就返回0，参见代码如下：

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = (int)A.size() - 1; i >= 2; --i) {
            if (A[i] < A[i - 1] + A[i - 2]) {
                return A[i] + A[i - 1] + A[i - 2];
            }
        }
        return 0;
    }
};

Github 同步地址:

#976

类似题目：

Largest Triangle Area

参考资料：

https://leetcode.com/problems/largest-perimeter-triangle/

https://leetcode.com/problems/largest-perimeter-triangle/discuss/217972/C%2B%2B-4-lines-O(n-log-n)

https://leetcode.com/problems/largest-perimeter-triangle/discuss/217988/JavaC%2B%2BPython-Sort-and-Try-Biggest

LeetCode All in One 题目讲解汇总(持续更新中...)