题目描述

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

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

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

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

样例

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

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

输入：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]

算法

(暴力枚举) $O(n^2)$

1. 暴力枚举矩形对，并求解重合区域最大的正方形面积。
2. 可以先求出重合区域的矩形长和宽，将横纵坐标分离，则可以利用求线段重合的方式求两个线段重合的长度。
3. 假设两个线段的端点分别为 $[l_1, r_1]$ 和 $[l_2, r_2]$，则重合的长度为 $\min(r_1, r_2) - \max(l_1, l_2)$，如果为负数，则不重合。

时间复杂度

• 矩形对共有 $O(n^2)$ 个，每对的求解时间为常数，故总时间复杂度为 $O(n^2)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
public:
    LL largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) {
        const int n = bottomLeft.size();

        LL ans = 0;

        for (int i = 0; i < n; i++) {
            const auto &b1 = bottomLeft[i];
            const auto &t1 = topRight[i];

            for (int j = i + 1; j < n; j++) {
                const auto &b2 = bottomLeft[j];
                const auto &t2 = topRight[j];

                int w = max(0, min(t1[0], t2[0]) - max(b1[0], b2[0]));
                int h = max(0, min(t1[1], t2[1]) - max(b1[1], b2[1]));

                int sz = min(w, h);

                ans = max(ans, (LL)(sz) * sz);
            }
        }

        return ans;
    }
};