自学内容网 自学内容网

【LeetCode每日一题】LeetCode 976.三角形的最大周长

LeetCode 976.三角形的最大周长

题目描述

给定一个包含非负整数的数组 nums,其中每个元素表示一个线段的长度。你需要从中选出三个线段,组成一个三角形,使得三角形的周长最大,并返回这个最大周长。如果无法组成三角形,返回 0。

三角形成立的条件:
  • 任意两边之和大于第三边。

Java 实现代码

import java.util.Arrays;

public 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];
            }
        }
        
        // 如果找不到有效的三角形,返回0
        return 0;
    }
}

解题思路

  1. 排序:首先对数组进行排序,确保最大的三条边在最后。通过排序,可以减少检查所有可能组合的次数,因为从大到小遍历,找到符合条件的三条边即可。
  2. 检查三角形成立条件:从排序后的数组末尾开始,检查当前三条边是否能构成一个三角形,即 nums[i-2] + nums[i-1] > nums[i]。如果满足条件,返回这三条边的周长。
  3. 返回结果:如果没有找到符合条件的三条边,则返回 0。

复杂度分析

  • 时间复杂度:O(n log n),其中 n 是数组的长度。主要由排序操作决定。
  • 空间复杂度:O(1),我们只用了常数的额外空间。

举例说明执行过程

假设输入数组 nums = [2, 1, 3, 4]

  1. 排序后的数组:[1, 2, 3, 4]

  2. 检查从后往前的三个数:

    • 第一次检查:nums[2] = 3, nums[3] = 4nums[1] = 22 + 3 > 4,符合三角形条件,返回周长 2 + 3 + 4 = 9

原文地址:https://blog.csdn.net/qq_14815605/article/details/144350496

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!