思路:

题目的主要信息:

  • 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;
    }
};

复杂度分析:

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