leetcode
leetcode 851 ~ 900
三角形的最大周长

三角形的最大周长

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 17.0 MB


/*
 思路:
 1. 先对数组进行排序。
 2. 使用Java Stream API,从后向前查找第一个可以形成三角形的三条边。
 3. 三角形的判定条件是任意两边之和大于第三边。
 4. 如果找到这样的三个边长,则返回它们的周长,否则返回0。
*/

import java.util.Arrays;

public class Solution {
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums); // 对数组进行排序
        return IntStream.range(0, nums.length - 2) // 使用流进行遍历
                .map(i -> nums[nums.length - 3 - i] + nums[nums.length - 2 - i] + nums[nums.length - 1 - i]) // 计算周长
                .filter(p -> p > 2 * nums[nums.length - 1 - p / 3]) // 过滤出满足条件的三角形
                .findFirst() // 获取第一个满足条件的周长
                .orElse(0); // 如果没有找到,返回0
    }
}

解释

方法:

为了形成一个非零面积的三角形,任意两边之和必须大于第三边。这可以通过排序数组确保最大的两个数的和大于第三个数来达成。首先对数组排序,然后从数组的末尾开始,检查每一组连续的三个数是否能形成一个三角形。检查的条件是:若第三大的数和第二大的数之和大于最大的数,则这三个数可以构成三角形。如果找到这样的组合,则返回这三个数的和作为最大周长。如果遍历结束仍未找到有效的三角形,则返回0。

时间复杂度:

O(n log n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在寻找可以形成三角形的三条边时,从数组的最大值开始向前检查是一个有效的方法?
从数组的最大值开始向前检查可以快速找到可能的最大周长的三角形。因为三角形的周长是由边长决定的,如果我们从最大的数开始检查,能够确保一旦找到符合条件的三个数,它们的周长一定是所有可能三角形中最大的。这种方法效率高,并且避免了不必要的检查。
🦆
在此算法中,如何保证找到的三条边确实可以形成面积不为零的三角形?
根据三角形的形成条件,任意两边之和必须大于第三边。在算法中,通过检查排序后连续的三个数,确保第三大的数和第二大的数之和大于最大的数,来保证这三个数可以形成一个非零面积的三角形。因为如果两边之和仅等于第三边,三角形就会退化成一条线,面积为零。
🦆
算法中提到,如果遍历结束仍未找到有效的三角形,则返回0。这是否意味着对于所有输入数组,该算法总是能够正确判断是否能形成至少一个有效的三角形?
是的,该算法能够正确判断是否能形成至少一个有效的三角形。算法通过系统地检查所有可能的连续三个数的组合,确保没有遗漏。如果数组中存在至少一组能形成三角形的三个数,算法会返回最大的周长。如果没有找到任何有效组合,则返回0,表示无法形成三角形。
🦆
如果数组中存在相同长度的边,这是否会影响算法的判断逻辑或结果?
在数组中存在相同长度的边并不会影响算法的判断逻辑或结果。算法只关心是否满足三角形的形成条件,即任意两边之和大于第三边。相同长度的边可以参与形成三角形,只要它们与其他边组合满足条件。因此,相同长度的边只会扩大可能形成三角形的组合数量,而不会影响算法的基本逻辑。

相关问题

最大三角形面积

给你一个由 X-Y 平面上的点组成的数组 points ,其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形,返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案

 

示例 1:

输入:points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出:2.00000
解释:输入中的 5 个点如上图所示,红色的三角形面积最大。

示例 2:

输入:points = [[1,0],[0,0],[0,1]]
输出:0.50000

 

提示:

  • 3 <= points.length <= 50
  • -50 <= xi, yi <= 50
  • 给出的所有点 互不相同