在线编程--46.最大矩形面积-阿里云开发者社区

开发者社区> 云计算> 正文

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

简介: 记录并分享自己的做题想法及源码,由于在此之前从没有使用过Java,而在线编程只能用java,因此边学编写,代码比较粗糙,欢迎提出建议,帮助蓬莱松进行改进,在此先谢谢大家啦。。。

题目

有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

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章