Largest Perimeter Triangle

https://leetcode.com/problems/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.

Thoughts

1. 三角形周长最大，也就是尽量让三条边大，并且满足任意两条边大于第三条边。

2. 因为要比大小，先排序。从大到小遍历，假定已经遍历到了i并把它作为一条边, 因为要找两条边和大于i的，则只能是剩下中的两条最大边i-1和i-2作为剩下两条边。验证i-1和i-2的和是否大于i, 满足则i, i-1和i-2即所求。

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

Analysis

时间复杂度O(NlgN).