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

探寻矩形交集中的最大正方形面积

在算法与数据结构的探索之路上，二维平面几何问题一直占据着独特的地位，它们不仅考验我们的空间思维能力，还要求我们能够巧妙地运用算法逻辑。今天，我们将深入剖析一道极具代表性的二维平面几何算法题 —— 在多个矩形的交集中，寻找能够容纳的最大正方形面积。

一、题目剖析

在二维平面上，给定n个矩形。通过两个下标从 0 开始的二维整数数组bottomLeft和topRight来描述这些矩形，两个数组的大小均为n x 2。其中，bottomLeft[i]和topRight[i]分别代表第i个矩形的左下角和右上角坐标。我们的任务是选择由两个矩形交集形成的区域，并找出能够放入该区域内的最大正方形面积。若矩形之间不存在任何交集区域，返回 0。

二、解题思路

解决这个问题的关键在于清晰地计算出每两个矩形的交集区域，进而确定交集中能容纳的最大正方形。具体步骤如下：

1. 遍历所有矩形对：使用双重循环遍历所有矩形组合，这样可以确保对每一对矩形都进行分析。
2. 计算交集区域边界：对于每一对矩形，通过比较它们的左下角和右上角坐标，确定交集区域的左、右、上、下边界。具体而言，交集区域的左边界是两个矩形左边界的较大值，右边界是两个矩形右边界的较小值，上边界是两个矩形上边界的较小值，下边界是两个矩形下边界的较大值。
3. 检查交集是否存在：通过判断左边界是否小于右边界，且下边界是否小于上边界，来确定两个矩形是否存在交集。若满足这两个条件，则说明存在交集区域。
4. 确定最大正方形边长：在存在交集的情况下，计算交集区域的宽度和高度，取两者中的较小值作为最大正方形的边长。这是因为正方形的边长受限于交集区域的最小维度。
5. 计算并更新最大面积：根据确定的边长计算正方形的面积，并与当前记录的最大面积进行比较，更新最大面积值。

三、代码实现

class Solution {public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {long maxArea = 0;int n = bottomLeft.length;for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {// 计算两个矩形交集的边界int left = Math.max(bottomLeft[i][0], bottomLeft[j][0]);int right = Math.min(topRight[i][0], topRight[j][0]);int bottom = Math.max(bottomLeft[i][1], bottomLeft[j][1]);int top = Math.min(topRight[i][1], topRight[j][1]);// 检查是否存在交集if (left < right && bottom < top) {// 计算交集区域的宽度和高度int width = right - left;int height = top - bottom;// 确定交集区域内可容纳的最大正方形边长int side = Math.min(width, height);// 计算正方形面积long area = (long) side * side;// 更新最大面积maxArea = Math.max(maxArea, area);}}}return maxArea;}
}

四、复杂度分析

1. 时间复杂度：算法的时间复杂度为 \(O(n^2)\)，其中n是矩形的数量。这是因为我们需要通过双重循环遍历所有的矩形对，对于每一对矩形，计算交集和最大正方形面积的操作时间复杂度为常数级。
2. 空间复杂度：算法的空间复杂度为 \(O(1)\)，在整个计算过程中，只使用了常数级别的额外空间，用于存储中间计算结果和最大面积值。

五、总结

这道题目通过矩形交集和正方形面积的计算，巧妙地融合了几何知识和算法逻辑。解题过程中，我们不仅加深了对二维平面坐标系统的理解，还进一步熟悉了嵌套循环、条件判断和数学运算在算法设计中的应用。希望通过本文的讲解，读者能对这类问题有更深入的认识，提升解决算法问题的能力。