LeetCode：3047. 求交集区域内的最大正方形面积（Java 枚举）

目录

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

题目描述：

原理思路：

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

题目描述：

        在二维平面上存在 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 <= 103
• bottomLeft[i].length == topRight[i].length == 2
• 1 <= bottomLeft[i][0], bottomLeft[i][1] <= 107
• 1 <= topRight[i][0], topRight[i][1] <= 107
• bottomLeft[i][0] < topRight[i][0]
• bottomLeft[i][1] < topRight[i][1]

实现代码与解析：

枚举

class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {



        long res = 0;

        int n = bottomLeft.length;

        for (int i = 0 ; i < n - 1; i++) {
            int ilx = bottomLeft[i][0];
            int ily = bottomLeft[i][1];

            int irx = topRight[i][0];
            int iry = topRight[i][1];

            for (int j = i + 1; j < n; j++) {
                int jlx = bottomLeft[j][0];
                int jly = bottomLeft[j][1];

                int jrx = topRight[j][0];
                int jry = topRight[j][1];

                int klx = Math.max(ilx, jlx);
                int kly = Math.max(ily, jly);

                int krx = Math.min(irx, jrx);
                int kry = Math.min(iry, jry);
                
                long c = Math.min(krx - klx, kry - kly);
                
                if (c > 0) {
                    res = Math.max(c * c, res);
                }
                
            }
        }

        return res;
    }
}

原理思路：

        枚举每一个矩阵组合，找到左下角最大的和右上角最小的，判断是否可以构成矩形，找到最小边即为可以放下的最大的正方形，对res进行更新。