46.最大矩形面积

题目概述

题目详情(点我)

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

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

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

题解

解题方法

• 查找相等的最大值

算法知识

• 排序算法

  • 时间复杂度: nlogn(依据排序算法而定)
  • 空间复杂度: 1

解题思路

审题

• int n : 木棍的数量
• long[] nums : 每个木棍的长度

题目要求

• 最大矩形的面积

思路

• 组成最大矩形 == 拿到最长的边
• 又因为矩形的对边相等, 所以需要两对两两相等的边

步骤

1. 定义变量

   • int x : 表示当前已找到的两两相等的边, 初始化为0
   • long[2] side : 存储找到的两条边的值

2. 使用排序算法对数组进行从小到大排序

3. 从索引n-1开始进行遍历, 寻找矩形需要的边

   • 判断当前边(nums[n-1]) 和前一条边(nums[n-2])是否相等, 若相等, 则加入到side数组里面, 并将x+1
   • 如果x的值==2, 则代表边找齐了, 则退出循环
4. 返回两条边的乘积side[0]*side[1];