Medium

题目描述

在二维平面上存在 n 个矩形，边都平行于 x 轴和 y 轴。给你两个二维整数数组 bottomLeft 和 topRight，其中 bottomLeft[i] = [a_i, b_i] 和 topRight[i] = [c_i, d_i] 分别表示第 i 个矩形的左下角和右上角坐标。

你需要找到能够放入至少两个矩形相交区域内的最大正方形面积。如果不存在这样的正方形，则返回 0。

示例 1：

输入：bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和 1 的相交区域或矩形 1 和 2 的相交区域。因此最大面积为 1。可以证明边长更大的正方形无法放入任何两个矩形的相交区域。

示例 2：

输入：bottomLeft = [[1,1],[1,3],[1,5]], topRight = [[5,5],[5,7],[5,9]]
输出：4
解释：边长为 2 的正方形可以放入矩形 0 和 1 的相交区域或矩形 1 和 2 的相交区域。因此最大面积为 2 * 2 = 4。可以证明边长更大的正方形无法放入任何两个矩形的相交区域。

示例 3：

输入：bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
输出：1
解释：边长为 1 的正方形可以放入任何两个矩形的相交区域。同时，不能放入更大的正方形，所以最大面积为 1。注意区域可以由超过 2 个矩形的交集形成。

示例 4：

输入：bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
输出：0
解释：没有任何一对矩形相交，因此答案为 0。

约束条件：

  • n == bottomLeft.length == topRight.length
  • 2 <= n <= 10³
  • bottomLeft[i].length == topRight[i].length == 2
  • 1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10⁷
  • 1 <= topRight[i][0], topRight[i][1] <= 10⁷
  • bottomLeft[i][0] < topRight[i][0]
  • bottomLeft[i][1] < topRight[i][1]

解题思路

解题思路

这道题的核心是计算两个矩形的相交区域，然后在相交区域内找到能容纳的最大正方形。

方法一：暴力枚举（推荐）

思路分析：

  1. 枚举所有矩形对： 遍历所有可能的矩形对 (i, j)，其中 i < j
  2. 计算相交区域： 对于每一对矩形，计算它们的相交区域
    • 相交区域的左下角：(max(left1, left2), max(bottom1, bottom2))
    • 相交区域的右上角：(min(right1, right2), min(top1, top2))
  3. 判断是否相交： 如果左下角坐标小于右上角坐标，则存在相交区域
  4. 计算最大正方形： 在相交区域内，最大正方形的边长等于相交矩形的宽度和高度的最小值
  5. 更新答案： 记录所有相交区域中能容纳的最大正方形面积

关键点：

  • 两个矩形相交的条件是：left1 < right2 && left2 < right1 && bottom1 < top2 && bottom2 < top1
  • 相交区域是一个矩形，最大正方形边长为 min(width, height)
  • 面积需要用 long long 类型存储，避免溢出

时间复杂度为 O(n²)，空间复杂度为 O(1)，这是最直接且高效的解法。

代码实现

class Solution {
public:
    long long largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) {
        int n = bottomLeft.size();
        long long maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算两个矩形的相交区域
                int left1 = bottomLeft[i][0], bottom1 = bottomLeft[i][1];
                int right1 = topRight[i][0], top1 = topRight[i][1];
                int left2 = bottomLeft[j][0], bottom2 = bottomLeft[j][1];
                int right2 = topRight[j][0], top2 = topRight[j][1];
                
                // 相交区域的左下角和右上角
                int intersectLeft = max(left1, left2);
                int intersectBottom = max(bottom1, bottom2);
                int intersectRight = min(right1, right2);
                int intersectTop = min(top1, top2);
                
                // 检查是否相交
                if (intersectLeft < intersectRight && intersectBottom < intersectTop) {
                    // 计算相交区域的宽度和高度
                    int width = intersectRight - intersectLeft;
                    int height = intersectTop - intersectBottom;
                    
                    // 最大正方形的边长是宽度和高度的最小值
                    int sideLength = min(width, height);
                    long long area = (long long)sideLength * sideLength;
                    maxArea = max(maxArea, area);
                }
            }
        }
        
        return maxArea;
    }
};

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        n = len(bottomLeft)
        max_area = 0
        
        for i in range(n):
            for j in range(i + 1, n):
                # 计算两个矩形的相交区域
                left1, bottom1 = bottomLeft[i]
                right1, top1 = topRight[i]
                left2, bottom2 = bottomLeft[j]
                right2, top2 = topRight[j]
                
                # 相交区域的左下角和右上角
                intersect_left = max(left1, left2)
                intersect_bottom = max(bottom1, bottom2)
                intersect_right = min(right1, right2)
                intersect_top = min(top1, top2)
                
                # 检查是否相交
                if intersect_left < intersect_right and intersect_bottom < intersect_top:
                    # 计算相交区域的宽度和高度
                    width = intersect_right - intersect_left
                    height = intersect_top - intersect_bottom
                    
                    # 最大正方形的边长是宽度和高度的最小值
                    side_length = min(width, height)
                    area = side_length * side_length
                    max_area = max(max_area, area)
        
        return max_area

public class Solution {
    public long LargestSquareArea(int[][] bottomLeft, int[][] topRight) {
        int n = bottomLeft.Length;
        long maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算两个矩形的相交区域
                int left1 = bottomLeft[i][0], bottom1 = bottomLeft[i][1];
                int right1 = topRight[i][0], top1 = topRight[i][1];
                int left2 = bottomLeft[j][0], bottom2 = bottomLeft[j][1];
                int right2 = topRight[j][0], top2 = topRight[j][1];
                
                // 相交区域的左下角和右上角
                int intersectLeft = Math.Max(left1, left2);
                int intersectBottom = Math.Max(bottom1, bottom2);
                int intersectRight = Math.Min(right1, right2);
                int intersectTop = Math.Min(top1, top2);
                
                // 检查是否相交
                if (intersectLeft < intersectRight && intersectBottom < intersectTop) {
                    // 计算相交区域的宽度和高度
                    int width = intersectRight - intersectLeft;
                    int height = intersectTop - intersectBottom;
                    
                    // 最大正方形的边长是宽度和高度的最小值
                    int sideLength = Math.Min(width, height);
                    long area = (long)sideLength * sideLength;
                    maxArea = Math.Max(maxArea, area);
                }
            }
        }
        
        return maxArea;
    }
}

var largestSquareArea = function(bottomLeft, topRight) {
    const n = bottomLeft.length;
    let maxArea = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            // 计算两个矩形的相交区域
            const [left1, bottom1] = bottomLeft[i];
            const [right1, top1] = topRight[i];
            const [left2, bottom2] = bottomLeft[j];
            const [right2, top2] = topRight[j];
            
            // 相交区域的左下角和右上角
            const intersectLeft = Math.max(left1, left2);
            const intersectBottom = Math.max(bottom1, bottom2);
            const intersectRight = Math.min(right1, right2);
            const intersectTop = Math.min(top1, top2);
            
            // 检查是否相交
            if (intersectLeft < intersectRight && intersectBottom < intersectTop) {
                // 计算相交区域的宽度和高度
                const width = intersectRight - intersectLeft;
                const height = intersectTop - intersectBottom;
                
                // 最大正方形的边长是宽度和高度的最小值
                const sideLength = Math.min(width, height);
                const area = sideLength * sideLength;
                maxArea = Math.max(maxArea, area);
            }
        }
    }
    
    return maxArea;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历所有可能的矩形对，共 C(n,2) = n(n-1)/2 对
空间复杂度O(1)只使用常数额外空间存储变量

相关题目