How is the longest diagonal determined in Maximum Area of Longest Diagonal Rectangle?

Calculate each rectangle's diagonal using sqrt(length^2 + width^2) and identify the maximum value. Ties are resolved using the largest area.

Can two rectangles have the same diagonal length?

Yes, when this happens, the rectangle with the larger area is returned according to problem rules.

Is there a way to avoid using floating point sqrt?

Compare squares of the diagonals instead of computing sqrt to maintain integer comparisons and improve precision.

What is the time complexity for this array-driven approach?

It is O(n) because each rectangle is scanned once and constant space is used for tracking maximums.

What common mistakes should I avoid for this diagonal comparison problem?

Do not prioritize area before diagonal length, avoid integer division rounding errors, and ensure tie-breaking logic is applied correctly.

#3000

Easy

auto_awesome数组·driven

LeetCode 题解工作台

对角线最长的矩形的面积

给你一个下标从 0 开始的二维整数数组 dimensions 。对于所有下标 i （ 0 ）， dimensions[i][0] 表示矩形 i 的长度，而 dimensions[i][1] 表示矩形 i 的宽度。返回对角线最长的矩形的面积。如果存在多个对角线长度相同的矩形，返回其中面积最…

数组

题目描述

给你一个下标从 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

lightbulb

解题思路

方法一：数学

根据勾股定理，矩形的对角线的平方为 $l^2 + w^2$ ，其中 $l$ 和 $w$ 分别是矩形的长度和宽度。

我们可以遍历所有矩形，计算它们的对角线长度的平方，并记录下最大的对角线长度和对应的面积。

遍历结束后，我们返回记录的最大面积。

时间复杂度 $O(n)$ ，其中 $n$ 是矩形的数量。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        ans = mx = 0
        for l, w in dimensions:
            t = l**2 + w**2
            if mx < t:
                mx = t
                ans = l * w
            elif mx == t:
                ans = max(ans, l * w)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each rectangle is processed once. Space complexity is O(1) extra space because only a few variables track maximums.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check that you are correctly computing diagonal lengths using the formula sqrt(length^2 + width^2).
question_mark
Clarify how you resolve ties when multiple rectangles have the same diagonal length.
question_mark
Consider edge cases with minimal or maximal rectangle dimensions to ensure correctness.

warning

常见陷阱

外企场景

error
Comparing areas without considering diagonal lengths first can lead to incorrect results.
error
Using integer division instead of floating point sqrt can cause precision errors when comparing diagonals.
error
Failing to update the maximum area for rectangles with equal diagonal lengths will return the wrong rectangle.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the rectangle with the shortest diagonal instead, prioritizing minimal area on ties.
arrow_right_alt
Return both the dimensions and area of the rectangle with the longest diagonal for additional output clarity.
arrow_right_alt
Compute diagonals without using sqrt by comparing squares of diagonals to avoid floating point calculations.

help

常见问题

外企场景

继续练习

#3002 移除后集合的最多元素数 #2997 使数组异或和等于 K 的最少操作次数 #2996 大于等于顺序前缀和的最小缺失整数