在线编程--46.最大矩形面积

题目

有n根木棍(4<=n<=1e5)，它们的长度分别为a1,a2,a3...an(1<=ai<=1e9)，现在请你从中挑选出4根木棍来组成一个矩形，问这个矩形的最大面积是多少

输入木棍数n和n个木棍长度

输出能组成的矩阵的最大面积

分析

拿到这个题，有以下重点：

• 矩形：意味着长和宽，同时面积为长*宽，从这个角度思考，能够成矩形，意味着得对所有木棍长度计数，找出个数大于2的数字
• 求最大面积，求最大面积意味着，找出最大的两个数，相乘就是最大面积；这个地方有个坑，就是最大的数字计数个数超过四个（包含4个）时，能够拼成最大面积的正方形。

通过以上分析，个人认为可以使用hash表来做。直接使用hash表，这样得到的时间复杂度的O(n)

源码

相关源码请参考：

https://code.aliyun.com/xinYe/aliProgrammaCode/blob/master/46.%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2%E9%9D%A2%E7%A7%AF.txt