三角形的最大周长

刺骨的言语ヽ痛彻心扉 2022-12-24 15:49 102阅读 0赞

> leetcode 976题 \[easy\]  
> 中：[三角形的最大周长][Link 1]  
> 英：[Largest Perimeter Triangle][Link 1]  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]

### 题解1 ###

1.  全排序 + 贪心
2.  时间复杂度：O(nlogn) 排序开销
3.  空间复杂度：O(logn) 快排递归栈开销
4.  实现
    
        /** * @param {number[]} A * @return {number} */
        var largestPerimeter = function(A) { 
            // 预处理（无）
        
            // 排序
            A.sort((a, b)=>a-b);
        
            // 贪心，从末尾遍历。判断 (最长边-第二长边) < 最短边 即可；（最长边+第二长边 > 最短边 已经天然满足）
            for(let i=A.length-1; i>=2; i--){ 
                if(A[i] - A[i-1] < A[i-2]) return A[i] + A[i-1] + A[i-2];
            }
        
            return 0;
        };

### 题解2 ###

1.  部分排序 + 贪心
2.  时间复杂度：O(n²) 主要看测试集，大部分情况下可以提前结束
3.  空间复杂度：O(1)
4.  实现
    
        /** * @param {number[]} A * @return {number} */
        var largestPerimeter = function(A) { 
        	// 预处理（无）
        	
            let AEndIdx = A.length-1;
            let headIdx = 0;
            let currMaxIdx = 0;
        
            // 先进行3轮排序
            for(let _=0; _<3; _++){ 
                for(let i=AEndIdx; i>headIdx; i--){ 
                    if(A[i] > A[currMaxIdx]) currMaxIdx = i;
                }
                [A[headIdx], A[currMaxIdx]] = [A[currMaxIdx], A[headIdx]];
                headIdx++;
                currMaxIdx = headIdx;
            }
            
            // 排序+比较
            while(true){ 
                // 找到符合题意的结果
                if(A[headIdx-3] - A[headIdx-2] < A[headIdx-1]) return A[headIdx-3] + A[headIdx-2] + A[headIdx-1];
        
                // 排序
                for(let i=AEndIdx; i>headIdx; i--){ 
                    if(A[i] > A[currMaxIdx]) currMaxIdx = i;
                }
                [A[headIdx], A[currMaxIdx]] = [A[currMaxIdx], A[headIdx]];
                headIdx++;
                currMaxIdx = headIdx;
        
                // 不能形成任何面积不为零的三角形
                if(headIdx > AEndIdx+1) return 0;
            }
            
        };

[Link 1]: https://leetcode-cn.com/problems/largest-perimeter-triangle/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NKMTU1MQ_size_16_color_FFFFFF_t_70]: /images/20221120/9174bce242f94c45b1a1135a4c3d4b78.png