牛牛与三角形题解

牛牛想从n个数中找出三个数来组成一个三角形，只不过牛牛想知道在所有的三角形的组成中，最大的三角形的周长减去最小的三角形的周长是多少？
牛牛不能够解决该问题，所以他想请你帮忙，给定n个数，返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值。
题目保证每组测试数据中都存在有三个数可以构成三角形。

题解：此题如果暴力求解，复杂度为n^3，必然会超时。找一个贪心策略，我们只需要进行从小到大的排序即可。然后三个三个数去判断是否可以构成一个三角形，不断地去寻找最大的三角形的周长和最小的三角形周长，最后返回即可。

时间复杂度：
空间复杂度：
参考代码如下：

class Solution {
public:
    int ok(int a, int b, int c)
    {
        return a + b > c && a + c > b && b + c > a;
    }
    /**
     * 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
     * @param n int整型 代表题目中的n
     * @param a int整型vector 代表n个数的大小
     * @return int整型
     */
    int solve(int n, vector<int> &a)
    {
        sort(a.begin(), a.end());
        int minn = 0x3f3f3f3f;
        int maxx = -1;
        for (int i = 2; i < n; i++)
        {
            if (ok(a[i], a[i - 1], a[i - 2]))
            {
                minn = min(minn, a[i] + a[i - 1] + a[i - 2]);
                maxx = max(maxx, a[i] + a[i - 1] + a[i - 2]);
            }
        }
        return maxx - minn;
    }
};