What is the pattern for solving the Largest Perimeter Triangle problem?

The problem is best approached using greedy choice and invariant validation. After sorting the array, check consecutive triplets for the triangle inequality to find the largest valid perimeter.

Why do we sort the array in descending order?

Sorting in descending order allows you to check the largest possible triangles first, optimizing for the largest perimeter while ensuring a valid triangle.

What should we do if no valid triangle is found?

If no valid triangle can be formed from any triplet, return 0 as the perimeter.

How do we check if three sides can form a valid triangle?

For three sides a, b, and c, they form a valid triangle if a + b > c, b + c > a, and a + c > b.

What is the time complexity of this approach?

The time complexity is O(N log N) due to the sorting step, and the space complexity is O(1) because no additional data structures are used.

#976

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

三角形的最大周长

给定由一些正数（代表长度）组成的数组 nums ，返回由其中三个长度组成的、面积不为零的三角形的最大周长。如果不能形成任何面积不为零的三角形，返回 0 。示例 1：输入： nums = [2,1,2] 输出： 5 解释：你可以用三个边长组成一个三角形:1 2 2。示例 2：输入： …

数组数学贪心排序

题目描述

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

lightbulb

解题思路

方法一：排序 + 贪心

我们不妨假设三角形的三条边长分别为 $a \leq b \leq c$ ，则三角形的面积不为零等价于 $a + b \gt c$ 。

我们可以枚举最大的边长 $c$ ，然后从剩下的边长中选取两个最大的边长 $a$ 和 $b$ ，如果 $a + b \gt c$ ，则可以构成一个面积不为零的三角形，且该三角形的周长最大；否则继续枚举下一个最大的边长 $c$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1, 1, -1):
            if (c := nums[i - 1] + nums[i - 2]) > nums[i]:
                return c + nums[i]
        return 0

speed

复杂度分析

指标	值
时间	O(N \log N)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Ability to recognize the greedy approach in problems involving optimization like this one.
question_mark
Understanding of the triangle inequality and how it applies to the formation of valid triangles.
question_mark
Efficient handling of sorting and triangle validation within the time complexity constraint.

warning

常见陷阱

外企场景

error
Forgetting to check the triangle inequality after sorting the array.
error
Not considering the largest possible triangle first, leading to suboptimal solutions.
error
Overcomplicating the problem by not leveraging sorting to reduce unnecessary checks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if we allow more than one set of triangle sides to form? Could we maximize the sum of perimeters?
arrow_right_alt
What if the array contains duplicate values? Does the approach still hold?
arrow_right_alt
What if instead of maximizing the perimeter, we need to minimize it? How does this change the solution?

help

常见问题

外企场景

继续练习

#910 最小差值 II #1363 形成三的最大倍数 #1561 你可以获得的最大硬币数目