Easy

题目描述

给定一个由正整数组成的数组 nums ，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，则返回 0。

示例 1：

输入：nums = [2,1,2]
输出：5
解释：你可以用三个边长组成三角形：1、2 和 2。

示例 2：

输入：nums = [1,2,1,10]
输出：0
解释：
不能用边长 1、1、2 来组成三角形。
不能用边长 1、1、10 来组成三角形。
不能用边长 1、2、10 来组成三角形。
由于无法用任何三个边长来组成一个面积不为零的三角形，所以我们返回 0。

提示：

  • 3 <= nums.length <= 10^4
  • 1 <= nums[i] <= 10^6

解题思路

解题思路

这道题的核心是利用三角形的性质：三角形两边之和必须大于第三边。

关键观察

  1. 贪心策略：要获得最大周长，我们希望三条边都尽可能长
  2. 排序优化：将数组从大到小排序后，从最大的三个数开始检查
  3. 三角形判定：对于三条边 a ≥ b ≥ c，只需要检查 b + c > a 即可

算法步骤

  1. 将数组降序排序
  2. 从前往后遍历，每次取连续的三个数作为候选边长
  3. 检查是否满足三角形条件：较小两边之和大于最大边
  4. 一旦找到满足条件的三角形，立即返回其周长（因为已经是最大的）
  5. 如果遍历完都没找到，返回 0

时间复杂度分析

  • 排序：O(n log n)
  • 遍历：O(n)
  • 总时间复杂度：O(n log n)

这种贪心方法是正确的，因为排序后的数组中，如果当前三个数不能构成三角形，那么包含更小数字的组合更不可能构成三角形。

代码实现

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

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        
        for i in range(len(nums) - 2):
            if nums[i + 1] + nums[i + 2] > nums[i]:
                return nums[i] + nums[i + 1] + nums[i + 2]
        
        return 0

public class Solution {
    public int LargestPerimeter(int[] nums) {
        Array.Sort(nums, (a, b) => b.CompareTo(a));
        
        for (int i = 0; i < nums.Length - 2; i++) {
            if (nums[i + 1] + nums[i + 2] > nums[i]) {
                return nums[i] + nums[i + 1] + nums[i + 2];
            }
        }
        
        return 0;
    }
}

var largestPerimeter = function(nums) {
    nums.sort((a, b) => b - a);
    
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i + 1] + nums[i + 2] > nums[i]) {
            return nums[i] + nums[i + 1] + nums[i + 2];
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(1)

说明：

  • 时间复杂度主要由排序决定，为 O(n log n)，遍历部分为 O(n)
  • 空间复杂度为 O(1)，只使用了常数额外空间（不考虑排序可能需要的栈空间）

相关题目