Leetcode每日一题：976.largest-perimeter-triangle（三角形的最大周长）

思路：首先肯定是排序，排序后只需要从一个方向上开始找即可；但这里我用的二分查找，确定A[i]和A[i-1]后我们需要在后面找一个数x，使得x为<A[i]+A[i+1]的最大的数，所以这种东西秒想到二分查找；后来通过后看评论，排序后直接从数组尾部开始遍历即可，因为要找最大的周长，并且A[i]肯定是>(A[i-1]-A[i-2])的，所以只需要找到某个A[i]，它能够满足A[i]<A[i-1]+A[i-2]即直接就是最大的周长；

速度还有有差别的

//法1：
//在a[l]和a[r]之间找到小于等于max的最大的值
int find(vector<int> &a, int l, int r, int max)
{
    if (l > r)
        return -1;
    if (a[l] > max)
        return -1;
    if (a[r] < max)
        return a[r];
    int pre = -1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (a[mid] == max)
        {
            return a[mid];
        }
        else if (a[mid] < max)
        {
            //说明绕圈了，这个值就是目标值
            if (pre == a[mid])
            {
                return a[mid];
            }
            pre = a[mid];
            l = mid;
        }
        else
        {
            pre = a[mid];
            r = mid;
        }
    }
    return a[l];
}

static bool cmp(int a, int b)
{
    return a < b;
}

int largestPerimeter(vector<int> &A)
{
    int len = A.size();
    if (len < 3)
        return 0;
    int res = 0;
    sort(A.begin(), A.end(), cmp);
    for (int i = 1; i < len; i++)
    {
        int min = A[i] - A[i - 1];
        int max = A[i] + A[i - 1];
        int tar = find(A, i + 1, len - 1, max - 1);
        if (tar == -1)
        {
            continue;
        }
        if (res < max + tar)
        {
            res = max + tar;
        }
    }
    return res;
}

//法2：直接从尾端查找
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = 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;
    }