题目描述
给你一个下标从 0 开始的二维整数数组 dimensions
。
对于所有下标 i
(0 <= i < dimensions.length
),dimensions[i][0]
表示矩形 i
的长度,而 dimensions[i][1]
表示矩形 i
的宽度。
返回对角线最 长 的矩形的 面积。如果存在多个对角线长度相同的矩形,返回面积最 大 的矩形的面积。
样例
输入:dimensions = [[9,3],[8,6]]
输出:48
解释:
下标 = 0,长度 = 9,宽度 = 3。对角线长度 = sqrt(9 * 9 + 3 * 3) = sqrt(90) ≈ 9.487。
下标 = 1,长度 = 8,宽度 = 6。对角线长度 = sqrt(8 * 8 + 6 * 6) = sqrt(100) = 10。
因此,下标为 1 的矩形对角线更长,所以返回面积 = 8 * 6 = 48。
输入:dimensions = [[3,4],[4,3]]
输出:12
解释:两个矩形的对角线长度相同,为 5,所以最大面积 = 12。
限制
1 <= dimensions.length <= 100
dimensions[i].length == 2
1 <= dimensions[i][0], dimensions[i][1] <= 100
算法
(枚举) $O(n)$
- 枚举每个矩形,按照题意找到对角线最长且面积尽可能大的矩形,并返回它的面积。
时间复杂度
- 遍历所有矩形一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
const int n = dimensions.size();
int ma_d = 0, ma_area = 0;
for (int i = 0; i < n; i++) {
int x = dimensions[i][0], y = dimensions[i][1];
int d = x * x + y * y, area = x * y;
if (ma_d < d) {
ma_d = d;
ma_area = area;
} else if (ma_d == d && ma_area < area) {
ma_area = area;
}
}
return ma_area;
}
};