【LetMeFly】976.三角形的最大周长：贪心(排序)
力扣题目链接：https://leetcode.cn/problems/largest-perimeter-triangle/
给定由一些正数（代表长度）组成的数组 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 <= 1041 <= nums[i] <= 106
解题方法：排序
将边长排序，采用贪心思维，先看最长边能不能用上：
选中所有边中的最长边，在此前提下，另外两边之和需要大于最长边。并且我们希望三角形周长最长，我们应该怎么选另外两条边？
很简单，不用动脑子就知道，另外两条边就选剩下的边中最长的两条。
如果发现最长边不能被用上，扔掉最长边，剩下的所有边仍然按照这个思路去挑选就好。
- 时间复杂度$O(n\log n)$，其中$n=len(nums)$
- 空间复杂度$O(\log n)$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
int largestPerimeter(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = nums.size() - 3; i >= 0; i--) {
if (nums[i] + nums[i + 1] > nums[i + 2]) {
return nums[i] + nums[i + 1] + nums[i + 2];
}
}
return 0;
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| '''
Author: LetMeFly
Date: 2025-09-28 13:21:46
LastEditors: LetMeFly.xyz
LastEditTime: 2025-09-28 13:30:31
'''
from typing import List
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums) - 3, -1, -1):
if nums[i] + nums[i + 1] > nums[i + 2]:
return nums[i] + nums[i + 1] + nums[i + 2]
return 0
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import java.util.Arrays;
class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums);
for (int i = nums.length - 3; i >= 0; i--) {
if (nums[i] + nums[i + 1] > nums[i + 2]) {
return nums[i] + nums[i + 1] + nums[i + 2];
}
}
return 0;
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
package main
import "sort"
func largestPerimeter(nums []int) int {
sort.Ints(nums)
for i := len(nums) - 3; i >= 0; i-- {
if nums[i] + nums[i + 1] > nums[i + 2] {
return nums[i] + nums[i + 1] + nums[i + 2]
}
}
return 0
}
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
impl Solution {
pub fn largest_perimeter(mut nums: Vec<i32>) -> i32 {
nums.sort();
for i in (0..nums.len()-2).rev() {
if nums[i] + nums[i + 1] > nums[i + 2] {
return nums[i] + nums[i + 1] + nums[i + 2];
}
}
0
}
}
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源