三角形的最大周长

题目

给定由一些正数(代表长度)组成的数组 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。

题解

分析

设三角形的三条边为 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
喜欢就支持一下吧
点赞10 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片快捷回复

    暂无评论内容