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

提示：

  • 矩形的对角线长度为 sqrt(length² + width²)。

解题思路

这道题要求找到拥有最长对角线的矩形的面积，如果有多个矩形拥有相同的最长对角线，则返回面积最大的矩形面积。

解题思路

核心思路是遍历所有矩形，计算每个矩形的对角线长度，并跟踪最长对角线对应的最大面积。

关键观察：

  1. 矩形对角线长度：sqrt(length² + width²)
  2. 为了避免浮点数计算的精度问题，我们可以比较 length² + width² 的值
  3. 当发现更长的对角线时，更新最大面积
  4. 当对角线长度相同时，选择面积更大的矩形

算法步骤：

  1. 初始化最长对角线的平方 maxDiagonalSquared = 0
  2. 初始化最大面积 maxArea = 0
  3. 遍历每个矩形：
    • 计算当前矩形的对角线平方值
    • 计算当前矩形的面积
    • 如果对角线更长，或者对角线相同但面积更大，则更新结果
  4. 返回最大面积

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        int maxDiagonalSquared = 0;
        int maxArea = 0;
        
        for (auto& dim : dimensions) {
            int length = dim[0], width = dim[1];
            int diagonalSquared = length * length + width * width;
            int area = length * width;
            
            if (diagonalSquared > maxDiagonalSquared || 
                (diagonalSquared == maxDiagonalSquared && area > maxArea)) {
                maxDiagonalSquared = diagonalSquared;
                maxArea = area;
            }
        }
        
        return maxArea;
    }
};

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        max_diagonal_squared = 0
        max_area = 0
        
        for length, width in dimensions:
            diagonal_squared = length * length + width * width
            area = length * width
            
            if (diagonal_squared > max_diagonal_squared or 
                (diagonal_squared == max_diagonal_squared and area > max_area)):
                max_diagonal_squared = diagonal_squared
                max_area = area
        
        return max_area

public class Solution {
    public int AreaOfMaxDiagonal(int[][] dimensions) {
        int maxDiagonalSquared = 0;
        int maxArea = 0;
        
        foreach (int[] dim in dimensions) {
            int length = dim[0], width = dim[1];
            int diagonalSquared = length * length + width * width;
            int area = length * width;
            
            if (diagonalSquared > maxDiagonalSquared || 
                (diagonalSquared == maxDiagonalSquared && area > maxArea)) {
                maxDiagonalSquared = diagonalSquared;
                maxArea = area;
            }
        }
        
        return maxArea;
    }
}

/**
 * @param {number[][]} dimensions
 * @return {number}
 */
var areaOfMaxDiagonal = function(dimensions) {
    let maxDiagonal = 0;
    let maxArea = 0;
    
    for (let [length, width] of dimensions) {
        let diagonal = length * length + width * width;
        let area = length * width;
        
        if (diagonal > maxDiagonal || (diagonal === maxDiagonal && area > maxArea)) {
            maxDiagonal = diagonal;
            maxArea = area;
        }
    }
    
    return maxArea;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历所有 n 个矩形，每个矩形的处理时间为 O(1)
空间复杂度O(1)只使用了常数个额外变量存储最长对角线和最大面积