贪心题目：三角形的最大周长

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题三角形的最大周长出处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≤1041 ≤ 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 cabc。为方便处理首先将数组nums \textit{nums}nums按升序排序。当最大边长c cc确定时为了使三角形的周长最大a aa和b bb应取最大值。对于i ≥ 2 i \ge 2i≥2当c nums [ i ] c \textit{nums}[i]cnums[i]时应取b nums [ i − 1 ] b \textit{nums}[i - 1]bnums[i−1]和a nums [ i − 2 ] a \textit{nums}[i - 2]anums[i−2]。如果此时a b c a b cabc则三角形的最大周长为a b c a b cabc。如果此时a b ≤ c a b \le cab≤c则a aa和b bb不能取更大值如果将a aa和b bb换成a ′ aa′和b ′ bb′则必有a ′ ≤ a a \le aa′≤ab ′ ≤ b b \le bb′≤ba ′ b ′ ≤ a b ≤ c a b \le a b \le ca′b′≤ab≤c因此不存在以c cc为最大边长的三角形。根据上述分析可以使用贪心的思想计算最大三角形周长。具体做法是首先将数组nums \textit{nums}nums按升序排序然后反向遍历数组nums \textit{nums}nums判断每组相邻三个元素是否可以组成三角形的三条边的边长如果可以则将三个元素之和作为最大三角形周长返回。如果遍历结束之后仍未遇到相邻三个元素可以组成三角形的三条边的边长则不能形成面积不为零的三角形返回0 00。代码classSolution{publicintlargestPerimeter(int[]nums){Arrays.sort(nums);for(intinums.length-3;i0;i--){if(nums[i]nums[i1]nums[i2]){returnnums[i]nums[i1]nums[i2];}}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)的递归调用栈空间。