题目
有n根木棍(4<=n<=1e5),它们的长度分别为a1,a2,a3...an(1<=ai<=1e9),现在请你从中挑选出4根木棍来组成一个矩形,问这个矩形的最大面积是多少
输入木棍数n和n个木棍长度
输出能组成的矩阵的最大面积
分析
拿到这个题,有以下重点:
- 矩形:意味着长和宽,同时面积为长*宽,从这个角度思考,能够成矩形,意味着得对所有木棍长度计数,找出个数大于2的数字
- 求最大面积,求最大面积意味着,找出最大的两个数,相乘就是最大面积;这个地方有个坑,就是最大的数字计数个数超过四个(包含4个)时,能够拼成最大面积的正方形。
通过以上分析,个人认为可以使用hash表来做。直接使用hash表,这样得到的时间复杂度的O(n)