题目

给定由一些正数（代表长度）组成的数组 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 <= 10^4
• 1 <= nums[i] <= 10^6

解题思路

• 第一步：排序 将整个数组 nums 按升序排序。这样做的好处有两个：
  • 方便我们应用上面提到的简化版三角不等式。
  • 让最大的元素都集中在数组的末尾，便于我们从大到小进行选择。
• 第二步：贪心遍历 我们从数组的末尾开始向前遍历，寻找第一个能构成三角形的组合。
  • 设当前遍历到的最大边的索引为 i（从 nums.length - 1 开始）。
  • 我们将 nums[i] 作为最长边 c。
  • 然后，我们选择与它相邻的两个较小的边，即 nums[i-1] 作为边 b，nums[i-2] 作为边 a。
  • 检查它们是否满足条件：nums[i-2] + nums[i-1] > nums[i]。
• 第三步：判断与返回
  • 如果满足 nums[i-2] + nums[i-1] > nums[i]：
    • 我们已经找到了一个有效的三角形。
    • 因为我们是从大到小遍历的，并且每次都选择当前最大的三个连续元素，所以这个三角形的周长 nums[i-2] + nums[i-1] + nums[i] 一定是所有可能组合中最大的。
    • 直接返回这个周长即可。
  • 如果不满足 nums[i-2] + nums[i-1] <= nums[i]：
    • 这说明 nums[i] 这条边相对于其他两条边来说“太长了”。
    • 由于 nums[i-1] 和 nums[i-2] 已经是除 nums[i] 之外最大的两条边了，如果连它们俩加起来都无法大于 nums[i]，那么数组中任何其他更小的两条边（例如 nums[i-3], nums[i-4] 等）的和也必然小于 nums[i]。
    • 因此，nums[i] 这条边不可能与数组中任何其他两条边构成三角形。我们可以放心地“抛弃” nums[i]，继续向前考察下一组，即将 nums[i-1] 作为最长边，继续检查 nums[i-3] + nums[i-2] > nums[i-1]。
• 第四步：处理边界情况
  • 如果循环结束（即 i 遍历到小于 2）都没有找到满足条件的组合，说明数组中任意三个数都无法构成三角形。此时，按题目要求返回 0。

具体代码

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {

        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = n - 1; i >= 2; --i)
        {
            if(nums[i - 2] + nums[i - 1] > nums[i])
            {
                return nums[i] + nums[i - 1] + nums[i - 2];
            }
        }
        return 0;
    }
};