文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题：三角形的最大周长
出处：976. 三角形的最大周长
难度
3 级
题目描述
要求
给定一个整数数组nums \texttt{nums}nums，返回从该数组中取出三个元素作为边长的面积不为零的最大三角形周长。如果不能形成任何面积不为零的三角形，返回0 \texttt{0}0。
示例
示例 1：
输入：nums = [2,1,2] \texttt{nums = [2,1,2]}nums = [2,1,2]
输出：5 \texttt{5}5
示例 2：
输入：nums = [1,2,1] \texttt{nums = [1,2,1]}nums = [1,2,1]
输出：0 \texttt{0}0
数据范围
- 3 ≤ nums.length ≤ 10 4 \texttt{3} \le \texttt{nums.length} \le \texttt{10}^\texttt{4}3≤nums.length≤104
- 1 ≤ nums[i] ≤ 10 6 \texttt{1} \le \texttt{nums[i]} \le \texttt{10}^\texttt{6}1≤nums[i]≤106
解法
思路和算法
由于整数数组nums \textit{nums}nums中的所有元素都大于零，因此数组nums \textit{nums}nums中的所有元素都是正整数。
三个正整数可以组成三角形的三条边的边长，等价于其中两个较小的正整数之和大于最大的正整数。用a aa、b bb和c cc表示三角形的三条边的边长，其中a ≤ b ≤ c a \le b \le ca≤b≤c，则应满足a + b > c a + b > ca+b>c。为方便处理，首先将数组nums \textit{nums}nums按升序排序。
当最大边长c cc确定时，为了使三角形的周长最大，a aa和b bb应取最大值。对于i ≥ 2 i \ge 2i≥2，当c = nums [ i ] c = \textit{nums}[i]c=nums[i]时，应取b = nums [ i − 1 ] b = \textit{nums}[i - 1]b=nums[i−1]和a = nums [ i − 2 ] a = \textit{nums}[i - 2]a=nums[i−2]。如果此时a + b > c a + b > ca+b>c，则三角形的最大周长为a + b + c a + b + ca+b+c。如果此时a + b ≤ c a + b \le ca+b≤c，则a aa和b bb不能取更大值，如果将a aa和b bb换成a ′ a'a′和b ′ b'b′，则必有a ′ ≤ a a' \le aa′≤a，b ′ ≤ b b' \le bb′≤b，a ′ + b ′ ≤ a + b ≤ c a' + b' \le a + b \le ca′+b′≤a+b≤c，因此不存在以c cc为最大边长的三角形。
根据上述分析，可以使用贪心的思想计算最大三角形周长。
具体做法是，首先将数组nums \textit{nums}nums按升序排序，然后反向遍历数组nums \textit{nums}nums，判断每组相邻三个元素是否可以组成三角形的三条边的边长，如果可以则将三个元素之和作为最大三角形周长返回。如果遍历结束之后仍未遇到相邻三个元素可以组成三角形的三条边的边长，则不能形成面积不为零的三角形，返回0 00。
代码
classSolution{publicintlargestPerimeter(int[]nums){Arrays.sort(nums);for(inti=nums.length-3;i>=0;i--){if(nums[i]+nums[i+1]>nums[i+2]){returnnums[i]+nums[i+1]+nums[i+2];}}return0;}}复杂度分析
时间复杂度：O ( n log n ) O(n \log n)O(nlogn)，其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( n log n ) O(n \log n)O(nlogn)的时间，排序之后遍历数组需要O ( n ) O(n)O(n)的时间，因此时间复杂度是O ( n log n ) O(n \log n)O(nlogn)。
空间复杂度：O ( log n ) O(\log n)O(logn)，其中n nn是数组nums \textit{nums}nums的长度。排序需要O ( log n ) O(\log n)O(logn)的递归调用栈空间。
