三角形的最大周长

发表于
本文字数： 853 阅读时长 ≈ 1 分钟

LeetCode每日一题，976. Largest Perimeter Triangle

先看题目描述

D6jgQf.png

大意就是给定一个数组 A，其中元素代表不同边的长度，让我们返回其中三条边能组成的三角形的最大周长

算法和思路

贪心+排序

我们假设三角形的边长满足 a <= b <= c，那么这三条边组成面积不为零的三角形的充分必要条件为 a + b > c

我们可以选择枚举三角形的最长边 c，从贪心策略的角度考虑，我们一定是选小于 c 的最大的两个数作为边长 a 和 b，此时最有可能满足 a + b > c，使得三条边能够组成一个三角形，且此时的三角形的周长最大

具体地，我们先对数组 A 进行排序，倒序枚举第 i 个数作为最长边，那么我们只需看其前两个数 A[i - 1] 和 A[i - 2]，判断 A[i - 1] + A[i - 2] 是否大于 A[i] 即可，如果能组成三角形那么我们就找到了周长最大的三角形，返回答案 A[i] + A[i- 1] + A[i - 2] 即可，如果对于任何数作为最长边都不存在面积不为零的三角形，那么就返回 0

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.*;

class Solution {
    public int largestPerimeter(int[] A) {
        int len = A.length;
        Arrays.sort(A);
        for (int i = len - 3; i >= 0; i--) {
            if (A[i] + A[i + 1] > A[i + 2]) {
                return A[i] + A[i + 1] + A[i + 2];
            }
        }
        return 0;
    }
}