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

难度: Medium

在二维平面上存在 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³
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]

Submission

运行时间: 172 ms

内存: 16.7 MB

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        d = 0
        n = len(bottomLeft)
        for i in range(n - 1):
            if (
                # 最大面积不足
                topRight[i][0] - bottomLeft[i][0] <= d
                or topRight[i][1] - bottomLeft[i][1] <= d
            ):
                continue

            for j in range(i + 1, n):
                if (
                    # 无交集
                    bottomLeft[j][0] >= topRight[i][0]
                    or bottomLeft[i][0] >= topRight[j][0]
                    or bottomLeft[j][1] >= topRight[i][1]
                    or bottomLeft[i][1] >= topRight[j][1]
                ):
                    continue
                bx = max(bottomLeft[i][0], bottomLeft[j][0])
                by = max(bottomLeft[i][1], bottomLeft[j][1])
                ux = min(topRight[i][0], topRight[j][0])
                uy = min(topRight[i][1], topRight[j][1])
                d = max(d, min(ux - bx, uy - by))
        return d ** 2

Explain

该题解采用了双重循环的方式，遍历所有矩形对以找出交集。首先，外层循环遍历每个矩形，内层循环则尝试与外层当前矩形找出可能的交集。在双层循环中，首先会检查两个矩形是否有交集，如果没有，则跳过当前的内层循环。如果存在交集，计算交集矩形的左下角和右上角坐标，然后计算此交集的可能最大正方形边长（选择宽度和高度中的较小值）。如果此边长大于已知的最大边长，则更新最大边长。最后，返回最大正方形的面积。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        d = 0  # 存储当前已知的最大正方形边长
        n = len(bottomLeft)  # 矩形数量
        for i in range(n - 1):
            # 如果当前矩形的边长小于或等于已知的最大边长，则不可能产生更大的正方形
            if (
                topRight[i][0] - bottomLeft[i][0] <= d
                or topRight[i][1] - bottomLeft[i][1] <= d
            ):
                continue
            for j in range(i + 1, n):
                # 检查矩形i与矩形j是否有交集
                if (
                    bottomLeft[j][0] >= topRight[i][0]
                    or bottomLeft[i][0] >= topRight[j][0]
                    or bottomLeft[j][1] >= topRight[i][1]
                    or bottomLeft[i][1] >= topRight[j][1]
                ):
                    continue
                # 计算交集区域的左下角和右上角
                bx = max(bottomLeft[i][0], bottomLeft[j][0])
                by = max(bottomLeft[i][1], bottomLeft[j][1])
                ux = min(topRight[i][0], topRight[j][0])
                uy = min(topRight[i][1], topRight[j][1])
                # 更新最大正方形的边长
                d = max(d, min(ux - bx, uy - by))
        return d ** 2  # 返回最大正方形的面积

Explore

使用坐标比较条件来判断两个矩形是否有交集是一种直观且高效的方法。由于矩形的对角坐标已知，可以通过比较这些坐标来快速确定两个矩形是否重叠。具体来说，通过比较一个矩形的右上角坐标是否在另一个矩形的左下角坐标的左侧或下侧，以及一个矩形的左下角坐标是否在另一个矩形的右上角坐标的右侧或上侧，可以直接判定两者是否重叠。这种方法不需要额外的数据结构或复杂计算，因此运行效率高，易于实现。

在计算两个有交集矩形的交集区域时，使用max函数确定交集区域的左下角坐标，使用min函数确定交集区域的右上角坐标，是为了正确获得重叠区域的边界。max函数用于比较两个矩形左下角的横坐标和纵坐标，选取较大的值，确保交集区域不会超出任何一个矩形的左下边界。同理，min函数比较两个矩形右上角的横坐标和纵坐标，选取较小的值，确保交集区域不会超出任何一个矩形的右上边界。这种方法确保了计算出的交集区域是两个矩形实际重叠的部分，且此区域是最大可能的重叠矩形，对求解问题至关重要。

实际上，外层循环在代码中是从0开始，直至n-1，这意味着它遍历每个矩形，以便与其后的每个其他矩形进行比较。这是一个常见的技巧，在处理成对比较时避免重复和不必要的比较。例如，当外层循环的索引为i时，内层循环的索引从i+1开始，确保每对矩形只比较一次。这种做法提高了算法的效率，避免了冗余计算，因为每对矩形只被比较一次而不是两次（i与j和j与i）。