对角线最长的矩形的面积

难度: Easy

给你一个下标从 0 开始的二维整数数组 dimensions。

对于所有下标 i（0 <= i < dimensions.length），dimensions[i][0] 表示矩形 i 的长度，而 dimensions[i][1] 表示矩形 i 的宽度。

返回对角线最长的矩形的面积。如果存在多个对角线长度相同的矩形，返回面积最大的矩形的面积。

示例 1：

输入：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。

示例 2：

输入：dimensions = [[3,4],[4,3]]
输出：12
解释：两个矩形的对角线长度相同，为 5，所以最大面积 = 12。

提示：

1 <= dimensions.length <= 100
dimensions[i].length == 2
1 <= dimensions[i][0], dimensions[i][1] <= 100

Submission

运行时间: 20 ms

内存: 16.7 MB

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        diag = [[x * x + y * y, x, y] for x, y in dimensions]
        diag.sort(key=lambda x: [x[0], x[1] * x[2]], reverse=True)
        return diag[0][1] * diag[0][2]

Explain

该题解首先通过计算每个矩形的对角线长度的平方来避免使用浮点运算。它创建一个新的列表，包含每个矩形的对角线长度平方、长度和宽度。接着，题解通过对这个列表进行排序，优先按对角线长度平方降序排列，如果对角线长度相同，则按面积降序排列。排序后，列表的第一个元素即是对角线最长且（在长度相同的情况下）面积最大的矩形。最后，计算并返回这个矩形的面积。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        # 创建一个列表，包含每个矩形的对角线长度的平方，长度和宽度
        diag = [[x * x + y * y, x, y] for x, y in dimensions]
        # 按对角线长度平方降序和面积降序排序
        diag.sort(key=lambda x: [x[0], x[1] * x[2]], reverse=True)
        # 返回对角线最长且面积最大的矩形的面积
        return diag[0][1] * diag[0][2]

Explore

使用对角线长度的平方而不是直接计算对角线长度进行比较主要是为了避免浮点数运算和可能导致的精度问题。对角线的长度涉及到平方根运算，这不仅增加了计算复杂度，还可能在比较时引入不必要的误差。使用平方值可以保持所有计算在整数域内，提高了程序的效率和准确性。

是的，这种排序方式确实能保证在对角线长度平方相同的情况下，能够得到最大的面积。lambda函数首先按对角线长度平方降序排列，如果存在对角线长度平方相同的矩形，则会按照面积降序进行次级排序。这样确保了在对角线长度平方相同的情况下，面积最大的矩形会被优先考虑。

在所有矩形对角线长度平方和面积都相同的极端情况下，由于所有的矩形都是等价的，从这些矩形中选择任何一个都可以满足题目的要求。因此，排序后直接返回列表中的第一个元素的面积即可。

如果输入的dimensions列表为空，则没有矩形可以进行处理，这通常应该被视为一个异常或特殊情况。在实际的函数实现中，应该添加适当的错误处理逻辑，例如可以在函数开始处检查列表是否为空，并抛出一个异常或返回一个特定的错误值（比如0或-1），以表示没有有效的输入数据。