题解 | #火柴拼图#

题目描述
牛妹有n根火柴，她想用这些火柴去拼正三角形或者正四边形。牛妹想让最后拼出的总面积尽可能大的，请你帮帮她。
返回一个Vector，Vector中存有两个数字。
其中最大面积S=Vector[0]*sqrt(3)/4+Vector[1]。

方法一：暴力求解

求解思路
对于本题目的求解，我们首先考虑到要构成正三角形或者正四边形，因此我们对火柴的长度进行计数统计，对于不同长度的火柴，判断其长度能否构成四边形或者三角形。我们自然想到，边长大的图形构成的面积可能会相对大一些，因此我们从长度一次遍历火柴，然后依次构成图形，并求出面积，我们维护一个最大值，然后遍历结束，我们输出这个最大值，即可得到本问题的答案。

图片说明

解题代码

class Solution {
public:
    vector<long> MaxArea(int n, vector<int>& Stick)
    {
        int mymax = 0; // 存储长度最大值
        for(int k:Stick)
        {
            mymax = max(mymax,k);
        }
        vector<long> myres(2);
        vector<int> a(mymax+1);
        for(int k:Stick)
        {
            a[k]++; // 对长度的数量进行记录
        }
        for(int i=mymax;i>=1;i--)
        {
            if(a[i]>=4) // 能够成四边形
            {
                int p = a[i]/4;
                a[i] -= p*4;
                myres[1] += p*(long)i*i; // 记录其面积值
            }
            if(a[i]>=3) // 能够成三角形
            {
                 myres[0] += (long)i*i; // 记录其面积值
            }
        }
        return myres; // 返回结果即可
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用数组a[n],因此空间复杂度为 $O(N)$

方法二：优化思想求解

求解思路
基于方法一，我们对其进行优化。方法一中发现每次求出长度最长的火柴时，再进行遍历后，还需要重新求解长度最大值，所以我们使用临时变量对其进行记录，这样可以减少查询最大值的时间，最后达到优化的效果。

图片说明

解题代码

class Solution {
public:
    vector<long> MaxArea(int n, vector<int>& Stick)
    {
        map<long, long> mymap;
        vector<long> myres(2,0);
        for (int i = 0; i < n; i++) // 存储长度
        {
         if (mymap.end() != mymap.find(Stick[i])) mymap[Stick[i]]++;
         else mymap.insert(pair<int, int>(Stick[i], 1));

        }
        for (auto it : mymap)
        {
           if(it.second>=4) // 构成四边形
           {
                int count = it.second/4;
                myres[1] += (long)(it.first)*(it.first)*count; // 更新结果
                it.second -= count*4;
            }
            if(it.second>=3) // 构成三角形
            {
                 myres[0] += (long)(it.first)*(it.first); // 更新结果
            }
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用mymap,因此空间复杂度为 $O(N)$