LeetCode 976. 三角形的最大周长
题目描述
题意分析
从正整数数组中选择三个不同位置的元素作为边长，组成面积大于零的三角形，返回最大周长；无法组成时返回 0。不同位置可以有相同边长。代码会先将输入数组原地排序。
解法：排序后从大到小找第一组合法边
核心思路
[!blue]
三边排序后设为
a <= b <= c。因为边长都为正，另外两条三角形不等式自动成立，只需检查a + b > c；相等时三边共线，不满足非退化要求。将数组升序排序，固定
nums[i]为最大边。它左边最大的两个元素是nums[i - 2]和nums[i - 1]：若这两项之和仍不大于最大边，换成其他两项也不会使和更大，因此以nums[i]为最大边的所有组合都无解，可以直接排除它。若这两项能组成三角形，它们也使当前最大边对应的周长达到最大。于是从右向左枚举最大边，第一次成功即可返回：更大下标的最大边已被证明无解；后续最大边以及它能搭配的两个最大元素，都不大于当前组合中对应的边，周长不可能更大。
解题步骤
- 将数组升序排序。
- 从
i = n - 1向左枚举最大边，直到i = 2，始终给另外两条边留下位置。- 检查
nums[i - 2] + nums[i - 1] > nums[i]。成立就返回这三项之和，否则继续减小i。- 所有候选都失败时返回 0，因为每一种可能的最大边都已排除。
代码实现
class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums);
for (int i = nums.length - 1; i >= 2; i--) {
// 固定最大边后，最大的两条较小边仍失败就可排除它
if (nums[i - 2] + nums[i - 1] > nums[i]) {
return nums[i - 2] + nums[i - 1] + nums[i];
}
}
return 0;
}
}
import "sort"
func largestPerimeter(nums []int) int {
sort.Ints(nums)
for i := len(nums) - 1; i >= 2; i-- {
// 固定最大边后，最大的两条较小边仍失败就可排除它
if nums[i-2]+nums[i-1] > nums[i] {
return nums[i-2] + nums[i-1] + nums[i]
}
}
return 0
}
复杂度分析
- 时间复杂度：$O(n\log n)$。排序占主导，枚举最大边最多扫描 $O(n)$ 次。
- 空间复杂度：扫描只使用 $O(1)$ 额外空间，总辅助空间取决于排序实现。
关键点总结
[!green]
- 固定最大边后，左边最大的两项同时是最容易满足三角形条件、周长也最大的选择。
- 最有利的搭配都失败，就能排除这个最大边，无需尝试其他配对。
- 从大到小枚举时，候选三项之和不会增加，因此第一组合法组合就是全局最优。
易错点总结
[!yellow]
- 必须使用严格不等号
>，等号只能组成退化三角形。- 不能只检查全局最大的三项；它们失败只能排除当前最大边，剩余元素中仍可能有解。
- 从小到大找到第一组就返回，只能保证存在三角形，无法保证周长最大。
- 不要对边长去重。相同长度但下标不同的元素可以分别作为不同的边。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 611. 有效三角形的个数 | 中等 | 同样应用排序后的三角形不等式，本题只取最大周长，原题统计所有合法组合。 |
| 补充题 156. 最小周长三角形 | 困难 | 改求最小周长后，不能简单反转比较方向并照搬最大周长的相邻三项证明。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！