976. 三角形的最大周长

🟢   🔖  贪心 数组 数学 排序  🔗 力扣 LeetCode

题目

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

Example 1:

Input: nums = [2,1,2]

Output: 5

Explanation: You can form a triangle with three side lengths: 1, 2, and 2.

Example 2:

Input: nums = [1,2,1,10]

Output: 0

Explanation:

You cannot use the side lengths 1, 1, and 2 to form a triangle.

You cannot use the side lengths 1, 1, and 10 to form a triangle.

You cannot use the side lengths 1, 2, and 10 to form a triangle.

As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

Constraints:

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

题目大意

给定由一些正数（代表长度）组成的数组 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. 排序处理:

   • 将数组 nums 按降序排序，保证大数在前。
   • 如果一个较大的边和其后两条边不能组成三角形，则和后续的更小边也无法组成三角形，因此从大到小判断能减少不必要的计算。

2. 构造三角形:

   • 从排序后的数组中，依次检查每三个连续的边 nums[i], nums[i+1], nums[i+2] 是否满足三角形不等式。

   • 检查条件: nums[i] < nums[i+1] + nums[i+2]。

     • 如果满足，则这三条边的和就是一个三角形的周长。
     • 由于数组已按降序排序，当前周长也一定是最大值，直接返回结果。

   • 如果循环结束仍未找到满足条件的三条边，则返回 0，表示无法构成任何三角形。

复杂度分析

• 时间复杂度: O(n log n)

  • 排序的时间复杂度为 O(n log n)。
  • 遍历数组检查三角形的时间复杂度为 O(n)，因此总体复杂度由排序决定。

• 空间复杂度: O(1)，排序原地进行，没有额外的空间开销。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var largestPerimeter = function (nums) {
	nums.sort((a, b) => b - a); // 按降序排序
	for (let i = 0; i < nums.length - 2; i++) {
		if (nums[i] < nums[i + 1] + nums[i + 2]) {
			return nums[i] + nums[i + 1] + nums[i + 2]; // 返回三条边的周长
		}
	}
	return 0; // 无法构成三角形
};

相关题目

题号	标题	题解	标签	难度	力扣
812	最大三角形面积	[✓]	几何 数组 数学	🟢	🀄️ 🔗