[LeetCode] 976. Largest Perimeter Triangle 最大周長的三角形

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: [2,1,2]

Output: 5

Example 2:

Input: [1,2,1]

Output: 0

Example 3:

Input: [3,2,3,4]

Output: 10

Example 4:

Input: [3,6,2,3]

Output: 8

Note:

3<=A.length<=10000

1<=A[i]<=10^6

這道題給了個正整數數組，讓從中選三個數當作三角形的三條邊，問能組成的三角形的最大周長是多少。因為要組成三角形，所以必須要滿足兩邊之和大於第三邊這一條性質，我們並不用去檢測所有的組合情況，而是只要判斷較短的兩邊之和是否大於最長的那條邊就可以了。雖然這道是 Easy 題目，但是 OJ 仍然不讓用暴力搜索法，遍歷任意三條邊是會超時的。所以只能想優化的解法，既然要周長最長，則肯定是選較大的數字先測比較好。這裡就先給數組排個序，然後從末尾開始，每次取出三個數字，先檢測能否組成三角形，可以的話直接返回周長，不行的話就繼續往前取，若都不行的話，就返回0，參見代碼如下：

class Solution {public:    int largestPerimeter(vector<int>& A) {        sort(A.begin(), A.end());        for (int i = (int)A.size() - 1; i >= 2; --i) {            if (A[i] < A[i - 1] + A[i - 2]) {                return A[i] + A[i - 1] + A[i - 2];            }        }        return 0;    }};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/976
類似題目：
Largest Triangle Area
參考資料：
https://leetcode.com/problems/largest-perimeter-triangle/
https://leetcode.com/problems/largest-perimeter-triangle/discuss/217972/C%2B%2B-4-lines-O(n-log-n)
https://leetcode.com/problems/largest-perimeter-triangle/discuss/217988/JavaC%2B%2BPython-Sort-and-Try-Biggest
LeetCode All in One 題目講解匯總(持續更新中...)