3000.对角线最长的矩形的面积：一次遍历

【LetMeFly】3000.对角线最长的矩形的面积：一次遍历

力扣题目链接：https://leetcode.cn/problems/maximum-area-of-longest-diagonal-rectangle/

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

解题方法：遍历维护最大值

使用一个变量l2维护最大的对角线长度的平方（避免无意义的开根号），遍历所有矩形：

• 如果当前矩形对角线长度的平方大于l2，则更新l2并直接更新答案为当前矩形的面积；
• 否则如果当前对角线长度的平方等于l2，则更新答案为当前矩形面积和答案的最大值。

时空复杂度分析

• 时间复杂度$O(len(dimensions))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-08-26 21:25:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-26 21:32:11
 */
class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        int ans = 0;
        int M = 0;
        for (vector<int>& d : dimensions) {
            int l2 = d[0] * d[0] + d[1] * d[1];
            if (l2 > M) {
                M = l2;
                ans = d[0] * d[1];
            } else if (l2 == M) {
                ans = max(ans, d[0] * d[1]);
            }
        }
        return ans;
    }
};

#if defined(_WIN32) || defined(__APPLE__)
/*
[[6,5],[8,6],[2,10],[8,1],[9,2],[3,5],[3,5]]
*/
int main() {
    string s;
    while (cin >> s) {
        vector<vector<int>> v = stringToVectorVector(s);
        Solution sol;
        cout << sol.areaOfMaxDiagonal(v) << endl;
    }
    return 0;
}
#endif

Python

'''
Author: LetMeFly
Date: 2025-08-26 21:25:10
LastEditors: LetMeFly.xyz
LastEditTime: 2025-08-26 21:34:38
'''
from typing import List
class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        ans = M = 0
        for a, b in dimensions:
            l2 = a * a + b * b
            if l2 > M:
                M = l2
                ans = a * b
            elif l2 == M:
                ans = max(ans, a * b)
        return ans

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-08-26 21:25:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-26 21:36:58
 */
class Solution {
    public int areaOfMaxDiagonal(int[][] dimensions) {
        int ans = 0;
        int M = 0;
        for (int[] d : dimensions) {
            int l2 = d[0] * d[0] + d[1] * d[1];
            if (l2 > M) {
                M = l2;
                ans = d[0] * d[1];
            } else if (l2 == M) {
                ans = Math.max(ans, d[0] * d[1]);
            }
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-08-26 21:25:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-26 21:36:14
 */
package main

func areaOfMaxDiagonal(dimensions [][]int) (ans int) {
    M := 0
    for _, d := range dimensions {
        l2 := d[0] * d[0] + d[1] * d[1]
        if l2 > M {
            M = l2
            ans = d[0] * d[1]
        } else if l2 == M {
            ans = max(ans, d[0] * d[1])
        }
    }
    return
}

Rust

/*
 * @Author: LetMeFly
 * @Date: 2025-08-26 21:25:10
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-08-26 21:40:59
 */
impl Solution {
    pub fn area_of_max_diagonal(dimensions: Vec<Vec<i32>>) -> i32 {
        let mut ans: i32 = 0;
        let mut m: i32 = 0;
        for d in dimensions.iter() {
            let l2: i32 = d[0] * d[0] + d[1] * d[1];
            if l2 > m {
                m = l2;
                ans = d[0] * d[1];
            } else if l2 == m {
                ans = ans.max(d[0] * d[1]);
            }
        }
        ans
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源