题目
给定由一些正数(代表长度)组成的数组 nums ,返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形,返回 0。
题目来源:https://leetcode.cn/problems/largest-perimeter-triangle
示例
示例 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 <= 104
1 <= nums[i] <= 106
3 <= nums.length <= 104
1 <= nums[i] <= 106
题解
分析
设三角形的三条边为 a,b,c。不失一般性,设三条边满足 1≤a≤b≤c
由于三角形两边之和大于第三边,a,b,c 需要满足下面三个不等式
a + b > c
a + c > b
b + c > a
上式中的 a+c>b 是必然成立的,因为 a+c≥a+b>b(注意 a 至少是 1)。
同样的,b+c>a 也必然成立,因为 b+c≥a+a>a(注意 a 至少是 1)。
所以只需考虑第一个式子 a+b>c。
枚举c,因为需要满足 a + b > c,所以 a + b 越大不等式就越容易成立并且三角形周长就越大。所以最大周长的三边 a,b,c 在数组排序后是相邻的
把 nums 从大到小排序,进行遍历,如果 nums[i+1] + nums[i+2] > nums[i] ,那么最大周长就为 nums[i] + nums[i+1] + nums[i+2]。
代码
class Solution {
public:
int largestPerimeter(vector<int>& nums) {
ranges::sort(nums, 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;
}
};
复杂度分析
- 时间复杂度:O(nlogn),其中 n 是 nums 的长度。瓶颈在排序上。
- 空间复杂度:O(1)。忽略排序的栈开销。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END




暂无评论内容