题解 | #最大四边形面积#

思路：

题目的主要信息：

• 从一个一维数组中任选4个数，组成四边形，求能组成的四边形的最大面积
• 返回结果与正确答案的误差应小于0.00001

性质1：能够组成四边形的四条边必然满足，三边之和大于第四边
性质2：四条边已知（a,b,c,d)的四边形，最大面积（形状不确定，因为四边形有不稳定性，只能求最大面积）为
，其中

因为我们要求的是最大面积，因此用上述公式计算面积也没错。

方法一：暴力法
具体做法：
四次遍历数组，找到所有四个数的组合，用性质1验证其是否是四边形，用性质2计算其最大面积。

class Solution {
public:
    double square(int a, int b, int c, int d){ //判断四边形是否存在且计算面积
        if(a + b + c < d || a + b + d < c || a + c + d < b || b + c + d < a) //三边之和要大于第四边 
            return 0.0;
        double sum = ((double) (a + b + c + d))/ 2;
        return sqrt((sum - a) * (sum - b) * (sum - c) * (sum -d)); //计算面积
    }
    double solve(vector<int>& a) {
        int n = a.size();
        double res = 0.0;
        for(int i = 0; i < n; i++) //四次遍历找到四条边
            for(int j = i + 1; j < n; j++)
                for(int k = j + 1; k < n; k++)
                    for(int m = k + 1; m < n; m++)
                        res = max(res, square(a[i], a[j], a[k], a[m]));
        return res;
    }
};

复杂度分析：

• 时间复杂度：，并非是，而是从一个n长度的数组选取不重复的四个数的组合数
• 空间复杂度：，常数个变量

方法二：排序法
具体做法：
因为要求能组成的四边形的最大面积，我们也知道确定的四边形四条边，上述公式就能算出该情况下的最大值，因此我们可以考虑直接取最大的四边形组成四边形，计算最大面积。所以我们对数组进行了排序，然后从后往前选取，只要算到了面积就跳出循环，避免了很多不必要的运算。

class Solution {
public:
    double solve(vector<int>& a) {
        sort(a.begin(), a.end()); //排序
        int n = a.size();
        double res = 0.0;
        for(int i = n - 1; i >= 0; i--)  //选取最后四个能组成四边形的组合
            for(int j = i - 1; j >= 0; j--)
                for(int k = j - 1; k >= 0; k--)
                    for(int m = k - 1; m >= 0; m--){
                        int x = a[i];
                        int b = a[j];
                        int c = a[k];
                        int d = a[m];
                        if(x + b + c > d && x + b + d > c && x + c + d > b && b + c + d > x){
                            double sum = ((double) (x + b + c + d)) / 2;
                            res = sqrt((sum - x) * (sum - b) * (sum - c) * (sum -d));
                            return res;
                        }
                    }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏复杂度还是这个，但是平均复杂度有所下降，因为不用全部遍历组合数，排序复杂度远小于组合数
• 空间复杂度：，常数个变量