leetcode976-三角形的最大周长

标签：周长 nums int 元素 相邻 leetcode976 最优 排序 三角形

第一反应是排序，然后瞎想了很多什么双指针、三指针的东西。看了评论区才豁然开朗。

“

为什么排序遍历相邻元素可行，有没有可能最优解为非相邻元素？（不会）

证明：反证 假设 a , b, c 为最优解，且存在a',b',满足 a < a' < b < b' < c（存在非相邻元素）

1. 由于 a + b > c，a < a', 有 a' + b > c，(a', b, c)优于(a, b, c),与(a, b, c)为最优解矛盾，故不存在a'
2. b'同理不存在 由于 a + b > c, b < b'，有a + b' > c，(a, b, c)为最优解矛盾，故不存在b'

因此最优解一定为排序后相邻元素

”

class Solution { public:     int largestPerimeter(vector<int>& nums) {         sort(nums.rbegin(),nums.rend());         for(int i=0;i<nums.size()-2;i++)         {             if(nums[i] < nums[i+1] + nums[i+2])             {                 return nums[i]+nums[i+1]+nums[i+2];             }         }         return 0;     } };

标签：周长,nums,int,元素,相邻,leetcode976,最优,排序,三角形
From： https://www.cnblogs.com/uacs2024/p/16650623.html