LeetCode 976. 三角形的最大周长
目录
题目描述
题意分析
输入是一个正整数数组，要从中挑出三个数当三角形的三条边，让周长尽可能大；如果一个合法三角形都拼不出来，返回
0。「能构成三角形」的判定条件是三角形不等式：任意两边之和严格大于第三边。注意是严格大于，两边之和恰好等于第三边时三点共线，退化成一条线段，题目不认。
约束信号有两个。其一，数组元素是无序的，但三角形不等式本身只关心相对大小关系，与元素在数组里的位置无关，所以重排数组不影响答案，这就为排序打开了大门。其二，只要挑三个数，不要求它们在原数组里相邻或有序，选择完全自由。
边界上要注意：数组长度恰好为
3、所有元素相等、存在两边之和恰好等于第三边、以及元素呈斐波那契式增长导致任何三个数都拼不出三角形（这时必须返回0）。
解法：排序后从大到小找第一组合法边
核心思路
暴力做法是三重循环枚举所有三元组，对每组做三次不等式检验，合法就更新最大周长，复杂度 $O(n^3)$。数组长度到 $10^4$ 时完全不可接受。
第一个瓶颈是三次检验里有两次是白做的。把三条边按 $a \le b \le c$ 排好序后，$a + c > b$ 因为 $c \ge b$ 且 $a > 0$ 必然成立，$b + c > a$ 同理必然成立，只有 $a + b > c$ 才是真正的约束。所以先把整个数组升序排好，检验就只剩一条。
第二个瓶颈是枚举量。排好序后固定最大边的下标
i，另外两条边只能从0到i - 1里挑。要让 $a + b > c$ 尽量容易满足，同时周长 $a + b + c$ 尽量大，这两个目标指向同一个选择：把a和b取成i左边最大的两个数，也就是nums[i - 2]和nums[i - 1]。任何别的取法都同时让不等式更难满足、让周长更小，不可能更优。于是每个i只需检验一次。最后一步观察让枚举也能提前结束。设合法三元组的最大边下标为
i，它的周长上界就是 $nums[i-2] + nums[i-1] + nums[i]$；下标i越大，这个上界越大（数组已升序）。从右往左扫描时，凡是被跳过的下标j > i都已经证明「以nums[j]为最大边根本组不出三角形」，不存在任何合法解；而第一个通过检验的i给出的周长恰好等于它自己的上界。所以第一次成功就是全局最优，可以立刻返回。显式的不变量是：扫描到下标
i时，所有以下标大于i的元素作为最大边的三元组都已被证明不合法。这条不变量既保证了提前返回的正确性，也保证了循环走完后返回0是对的。
解题步骤
- 先对数组做升序排序。排序是后续所有简化的前提：它让「三条不等式」塌缩成一条，也让「最大边左边最大的两个数」变成简单的下标
i - 1和i - 2。- 从
i = n - 1开始向左枚举最大边的下标，循环下界是i >= 2。下界取2是因为最大边左边至少要留出两个元素，i再小就会读到负下标。- 对每个
i只检验nums[i - 2] + nums[i - 1] > nums[i]这一条。用严格大于而不是大于等于，是因为等号对应退化的共线情形。- 检验通过就立刻返回三者之和。之所以能立刻返回而不是继续找更大的，是因为右侧所有下标都已被证否，而当前下标给出的正是它能达到的最大周长。
- 循环自然结束说明每个下标都做不成最大边，返回
0。这个兜底分支必须写，否则函数没有返回值。以
nums = [3, 6, 2, 3]走一遍：升序排序后数组变成[2, 3, 3, 6]，n = 4。
i = 3时最大边是nums[3] = 6，另两条取nums[1] = 3和nums[2] = 3，检验 $3 + 3 = 6$，不满足严格大于6，跳过。此时已经证明：任何以6为最大边的三元组都不合法。
i = 2时最大边是nums[2] = 3，另两条取nums[0] = 2和nums[1] = 3，检验 $2 + 3 = 5 > 3$ 成立，返回周长 $2 + 3 + 3 = 8$。再看一个全否的例子
nums = [1, 2, 1, 10]：排序后是[1, 1, 2, 10]。i = 3检验 $1 + 2 = 3$ 不大于10，跳过；i = 2检验 $1 + 1 = 2$ 不大于2，等号不算，跳过。循环结束，返回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;
}
}
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)$，全部开销来自排序。排序之后的扫描每个下标只做一次常数级检验，最多走 $n - 2$ 步，相比排序可以忽略。
- 空间复杂度：$O(\log n)$，来自排序递归栈；如果换成不递归的原地排序则是 $O(1)$。算法本身只用了一个循环变量，没有开额外数组。
关键点总结
- 当约束只关心元素之间的相对大小、与位置无关时，排序几乎总是第一步。这题排序一次同时买到了两样东西：三条不等式化简成一条，以及「左边最大的两个数」变成常数时间可取。
- 「固定一个维度再论证另外两个维度的最优取法」是把 $O(n^3)$ 压到 $O(n)$ 的通用手法。这里固定最大边后，能证明另外两条边只有一种最优取法，枚举量立刻从平方降到常数。
- 提前返回必须配一句证明，否则就是碰运气。这题的证明是「被跳过的下标全都无解，而当前下标的取法已达到它的上界」，缺了任何一半都不足以支撑「第一次成功即全局最优」。
- 严格不等号和非严格不等号的区别在几何题里往往就是全部难点。退化三角形这个坑几乎每次都会被
[1, 1, 2]这类用例抓出来。- 面试视角：面试官常追问「如果改成统计能构成三角形的三元组数量呢」。那就是第 611 题，提前返回失效，需要固定最大边后用双指针在左侧区间上计数，复杂度升到 $O(n^2)$。能指出「求最大值可以贪心提前返回、求计数不行」，说明真的理解了提前返回依赖什么。
- 面试视角：这题在白板上最容易被扣分的地方是下标越界和无解兜底。落笔前先把
i >= 2的下界理由和return 0的位置说出来，比写完再补漏洞更从容。
易错点总结
- 错误写法：不排序就直接取相邻三元素检验。用例
[1, 10, 2, 3]→ 从右往左第一次检验nums[1] + nums[2] = 10 + 2 = 12 > nums[3] = 3成立，返回15，但这三个数里2 + 3 = 5远小于10，实际根本组不成三角形，正确答案是0。- 错误写法：三角形不等式写成
>=。用例[1, 2, 3]→ 排序后1 + 2 = 3被判为合法，返回周长6，但两边之和等于第三边时三点共线，正确答案是0。- 错误写法：从小到大扫描，找到第一组合法边就返回。用例
[1, 2, 2, 3, 4]→ 排序后最先遇到的合法三元组是(1, 2, 2)，返回5，而从大到小扫描会在(2, 3, 4)处返回9。- 错误写法：循环下界写成
i >= 0。用例[1, 1, 10]→i = 2检验1 + 1 = 2不大于10而跳过，i = 1时要读nums[-1]，直接数组越界崩溃。- 错误写法：只检验排序后最末尾的一组，不合法就返回
0。用例[1, 2, 2, 3, 4, 100]→ 末尾组3 + 4 = 7不大于100，直接返回0，而实际存在合法三元组(2, 3, 4)，正确答案是9。- 错误写法：把「最大周长」直接理解成「最大的三个数之和」，跳过不等式检验。用例
[1, 2, 2, 3, 4, 100]→ 返回3 + 4 + 100 = 107，但这三条边组不成三角形，正确答案是9。- 错误写法：固定最大边后，另外两条边从数组开头挑而不是紧邻左侧挑。用例
[1, 2, 2, 3, 4]→ 以4为最大边时取到1和2，1 + 2 = 3不大于4，误判4不能当最大边；以3为最大边时同样被误判，最终返回5而不是9。- 错误写法：为了不破坏输入而先拷贝一份排序，返回周长时却用原数组取值。用例
[3, 6, 2, 3]→ 在排序后的副本上于下标0、1、2找到合法边，却回原数组累加3 + 6 + 2 = 11，答案错成11而不是8。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 611. 有效三角形的个数 | 中等 | 同样是三角形不等式，但要统计数量，提前返回的贪心失效 |
| 455. 分发饼干 | 简单 | 两个数组各自排序后用双指针做贪心配对 |
| 179. 最大数 | 中等 | 贪心藏在自定义比较器里，排序规则本身需要证明传递性 |