M3047.求交集区域内的最大正方形面积

https://leetcode.cn/problems/find-the-largest-area-of-square-inside-two-rectangles/

在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight，两个数组的大小都是 n x 2 ，其中 bottomLeft[i] 和 topRight[i] 分别代表第 i 个矩形的 左下角 和 右上角 坐标。

我们定义向右的方向为 x 轴正半轴（x 坐标增加），向左的方向为 x 轴负半轴（x 坐标减少）。同样地，定义向上的方向为 y 轴正半轴（y 坐标增加），向下 的方向为 y 轴负半轴（y 坐标减少）。

你可以选择一个区域，该区域由两个矩形的交集形成。你需要找出能够放入该区域内的最大正方形面积，并选择最优解。

返回能够放入交集区域的正方形的最大可能面积，如果矩形之间不存在任何交集区域，则返回 0。

示例 1：

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

示例 2：

输入：bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1，矩形 1 和矩形 2，或所有三个矩形的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。
请注意，区域可以由多于两个矩形的交集构成。

示例 3：

输入：bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
输出：0
解释：不存在相交的矩形，因此，返回 0 。

提示：

n == bottomLeft.length == topRight.length
2 <= n <= 10^3
bottomLeft[i].length == topRight[i].length == 2
1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10^7
1 <= topRight[i][0], topRight[i][1] <= 10^7
bottomLeft[i][0] < topRight[i][0]
bottomLeft[i][1] < topRight[i][1]

这是一道几何问题，主要考察如何计算两个矩形的交集，并在该交集中找到最大的正方形。

解题思路

矩形交集的计算：对于两个矩形，设第一个矩形的左下角为 $(a x_{1}, a y_{1})$ ，右上角为 $(a x_{2}, a y_{2})$ ；第二个矩形的左下角为 $(b x_{1}, b y_{1})$ ，右上角为 $(b x_{2}, b y_{2})$ 。它们的交集也是一个矩形（或者不存在），其坐标范围如下：
- 交集左下角 $x$ ： $i x_{1} = max (a x_{1}, b x_{1})$
- 交集左下角 $y$ ： $i y_{1} = max (a y_{1}, b y_{1})$
- 交集右上角 $x$ ： $i x_{2} = min (a x_{2}, b x_{2})$
- 交集右上角 $y$ ： $i y_{2} = min (a y_{2}, b y_{2})$
判断交集有效性：交集的宽度 $w = i x_{2} - i x_{1}$ ，高度 $h = i y_{2} - i y_{1}$ 。只有当 $w > 0$ 且 $h > 0$ 时，这两个矩形才存在有效的重叠区域。
计算最大正方形：在一个宽为 $w$ 、高为 $h$ 的矩形区域内，能放入的最大正方形的边长受限于矩形的短边。因此，最大正方形边长 $s i d e = min (w, h)$ 。
遍历所有对：题目要求我们找任意两个矩形交集中的最大正方形。由于 $n$ 的范围较小 ( $2 \leq n \leq 1000$ )，我们可以直接使用双重循环遍历所有可能的矩形对 $(i, j)$ ，计算它们的交集，并更新全局的最大边长。时间复杂度为 $O (n^{2})$ ，在 $n = 1000$ 时计算量约为 $5 \times 10^{5}$ ，完全符合时间要求。

代码实现

python

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        n = len(bottomLeft)
        max_side = 0
        
        # 遍历所有矩形对 (i, j)
        for i in range(n):
            # 获取矩形 i 的坐标
            ax1, ay1 = bottomLeft[i]
            ax2, ay2 = topRight[i]
            
            for j in range(i + 1, n):
                # 获取矩形 j 的坐标
                bx1, by1 = bottomLeft[j]
                bx2, by2 = topRight[j]
                
                # 计算交集的左下角 (取最大值)
                inter_x1 = max(ax1, bx1)
                inter_y1 = max(ay1, by1)
                
                # 计算交集的右上角 (取最小值)
                inter_x2 = min(ax2, bx2)
                inter_y2 = min(ay2, by2)
                
                # 计算交集的宽和高
                width = inter_x2 - inter_x1
                height = inter_y2 - inter_y1
                
                # 如果存在有效交集
                if width > 0 and height > 0:
                    # 正方形边长由宽和高中的较小值决定
                    current_side = min(width, height)
                    # 更新最大边长
                    if current_side > max_side:
                        max_side = current_side
                        
        # 返回最大面积 (边长的平方)
        return max_side * max_side

复杂度分析

时间复杂度： $O (n^{2})$ 。我们需要遍历所有唯一的矩形对，对数约为 $\frac{n (n - 1)}{2}$ 。
空间复杂度： $O (1)$ 。除了存储输入外，我们只使用了常数个变量来存储坐标和最大值。

M3047.求交集区域内的最大正方形面积 ​

M3047.求交集区域内的最大正方形面积