题解 | #火柴拼图#

思路：

题目的主要信息：

• n根火柴，长度记录在数组Stick中，用这些火柴拼成正三角形或是正四边形
• 每一边只能选一根火柴，可以组成多个图形
• 求能够组成的图形面积和的最大值，返回一个二元的数组，其中，即数组第一个元素是所有三角形边的平方之和，第二个元素是所有正方形边的平方之和

方法一：贪心
具体做法：
我们都知道如果有6根相同长度的火柴，那么组成一个正方形的面积是大于组成两个正三角形的面积。因此我们采用贪心思想，尽可能多地优先组成正方形，剩下不足四条边再组成正三角形。

我们可以遍历火柴长度的数组，用另一个数组记录每种长度出现的次数，并记录最大长度。
然后我们遍历刚刚记录的数组，对于每种长度，优先组成四边形，然后再组成三角形，求其面积和。

class Solution {
public:
    vector<long> MaxArea(int n, vector<int>& Stick) {
        vector<long> res(2);
        vector<int> cnt(100001);
        int maxlen = 0;
        for(int i = 0; i < n; i++){
            maxlen = max(maxlen, Stick[i]); //找到最长的火柴
            cnt[Stick[i]]++;  //每种长度火柴有多少
        }
        for(int i = 1; i <= maxlen; i++){
            if(cnt[i] != 0){
                int temp1 = cnt[i] / 4; //四边形面积最大，优先组成四边形
                int temp2 = cnt[i] % 4 / 3; //剩下的再组成三角形
                res[1] += (long) i * i * temp1;
                res[0] += (long) i * i * temp2;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，两次遍历，第一次遍历个数，第二次遍历数组最大值
• 空间复杂度：，最坏情况下，全是不同的长度

方法二：哈希表改进贪心
具体做法：
利用哈希表改进上述方法一。
火柴长度和对应数量可以存入哈希表，之后遍历哈希表，对于每种长度，优先组成正方形，再来三角形。

class Solution {
public:
    vector<long> MaxArea(int n, vector<int>& Stick) {
        vector<long> res(2);
        unordered_map<int, int> mp;
        for(int i = 0; i < n; i++){ //利用哈希表记录每种长度有多少
            mp[Stick[i]]++;
        }
        for(auto& it: mp){
            if(it.second != 0){
                int temp1 = it.second / 4; //四边形面积最大，优先组成四边形
                int temp2 = it.second % 4 / 3; //剩下的再组成三角形
                res[1] += (long) it.first * it.first * temp1;
                res[0] += (long) it.first * it.first * temp2;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，遍历数组，遍历哈希表最大为
• 空间复杂度：，最坏情况下，全是不同的长度