976. 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.

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation