列表

详情

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

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

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: long long largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) { } };

java 解法, 执行用时: 72 ms, 内存消耗: 44.1 MB, 提交时间: 2024-02-26 11:02:06 

class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        long ans = 0;
        for (int i = 0; i < bottomLeft.length; i++) {  // 第一个矩形
            int[] b1 = bottomLeft[i];  // 左下角
            int[] t1 = topRight[i];    // 右上角
            for (int j = i + 1; j < bottomLeft.length; j++) {  // 第二个矩形
                int[] b2 = bottomLeft[j];  // 左下角
                int[] t2 = topRight[j];    // 右上角
                int height = Math.min(t1[1], t2[1]) - Math.max(b1[1], b2[1]);   // 交集部分的矩形高度(右上纵坐标-左下纵坐标)
                int width = Math.min(t1[0], t2[0]) - Math.max(b1[0], b2[0]);    // 交集部分的矩形宽度(右上横坐标-左下横坐标)
                int size = Math.min(width, height);
                if (size > 0) {
                    ans = Math.max(ans, (long) size * size);
                }
            }
        }
        return ans;
    }
}

golang 解法, 执行用时: 116 ms, 内存消耗: 6.8 MB, 提交时间: 2024-02-26 10:55:26 

func largestSquareArea(bottomLeft, topRight [][]int) (ans int64) {
	for i, b1 := range bottomLeft {
		t1 := topRight[i]
		for j := i + 1; j < len(bottomLeft); j++ {
			b2, t2 := bottomLeft[j], topRight[j]
			height := min(t1[1], t2[1]) - max(b1[1], b2[1])
			width := min(t1[0], t2[0]) - max(b1[0], b2[0])
			size := min(width, height)
			if size > 0 {
				ans = max(ans, int64(size)*int64(size))
			}
		}
	}
	return
}

python3 解法, 执行用时: 5436 ms, 内存消耗: 17.2 MB, 提交时间: 2024-02-26 10:55:00 

# 求出交集左下角和右上角坐标
class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        ans = 0
        for ((x1, y1), (x2, y2)), ((x3, y3), (x4, y4)) in combinations(zip(bottomLeft, topRight), 2):
            width = min(x2, x4) - max(x1, x3)  # 注：改成用 if-else 计算 min 和 max 会更快
            height = min(y2, y4) - max(y1, y3)
            size = min(width, height)
            if size > 0:
                ans = max(ans, size * size)
        return ans

上一题

© 2024 leetcode.cn