求交集区域内的最大正方形面积
难度:
标签:
题目描述
There exist n rectangles in a 2D plane. You are given two 0-indexed 2D integer arrays bottomLeft and topRight, both of size n x 2, where bottomLeft[i] and topRight[i] represent the bottom-left and top-right coordinates of the ith rectangle respectively.
You can select a region formed from the intersection of two of the given rectangles. You need to find the largest area of a square that can fit inside this region if you select the region optimally.
Return the largest possible area of a square, or 0 if there do not exist any intersecting regions between the rectangles.
Example 1:
Input: bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]] Output: 1 Explanation: A square with side length 1 can fit inside either the intersecting region of rectangle 0 and rectangle 1, or the intersecting region of rectangle 1 and rectangle 2. Hence the largest area is side * side which is 1 * 1 == 1. It can be shown that a square with a greater side length can not fit inside any intersecting region.
Example 2:
Input: bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]] Output: 1 Explanation: A square with side length 1 can fit inside either the intersecting region of rectangle 0 and rectangle 1, the intersecting region of rectangle 1 and rectangle 2, or the intersection region of all 3 rectangles. Hence the largest area is side * side which is 1 * 1 == 1. It can be shown that a square with a greater side length can not fit inside any intersecting region. Note that the region can be formed by the intersection of more than 2 rectangles.
Example 3:
Input: bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]] Output: 0 Explanation: No pair of rectangles intersect, hence, we return 0.
Constraints:
n == bottomLeft.length == topRight.length2 <= n <= 103bottomLeft[i].length == topRight[i].length == 21 <= bottomLeft[i][0], bottomLeft[i][1] <= 1071 <= topRight[i][0], topRight[i][1] <= 107bottomLeft[i][0] < topRight[i][0]bottomLeft[i][1] < topRight[i][1]
代码结果
运行时间: 172 ms, 内存: 16.7 MB
/*
* 思路：
* 使用Java Stream API来简化代码逻辑。
* 我们可以利用嵌套的forEach循环来遍历所有的矩形组合。
* 对于每对矩形，计算交集区域的坐标并更新最大正方形的边长。
*/
import java.util.stream.IntStream;
public int maxSquareArea(int[][] bottomLeft, int[][] topRight) {
int n = bottomLeft.length;
int[] maxSquareSide = {0};
IntStream.range(0, n).forEach(i -> {
IntStream.range(i + 1, n).forEach(j -> {
int leftX = Math.max(bottomLeft[i][0], bottomLeft[j][0]);
int bottomY = Math.max(bottomLeft[i][1], bottomLeft[j][1]);
int rightX = Math.min(topRight[i][0], topRight[j][0]);
int topY = Math.min(topRight[i][1], topRight[j][1]);
if (leftX < rightX && bottomY < topY) {
int side = Math.min(rightX - leftX, topY - bottomY);
maxSquareSide[0] = Math.max(maxSquareSide[0], side);
}
});
});
return maxSquareSide[0] * maxSquareSide[0];
}
解释
方法:
该题解采用了双重循环的方式，遍历所有矩形对以找出交集。首先，外层循环遍历每个矩形，内层循环则尝试与外层当前矩形找出可能的交集。在双层循环中，首先会检查两个矩形是否有交集，如果没有，则跳过当前的内层循环。如果存在交集，计算交集矩形的左下角和右上角坐标，然后计算此交集的可能最大正方形边长（选择宽度和高度中的较小值）。如果此边长大于已知的最大边长，则更新最大边长。最后，返回最大正方形的面积。
时间复杂度:
O(n^2)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在判断两个矩形是否有交集时，使用的是坐标的比较条件而不是其他方法？
▷🦆
在计算交集区域的左下角和右上角坐标时，为什么选择使用max和min函数？这种选择对结果有什么影响？
▷🦆
在双重循环中，外层循环为何从n-1开始而非从0开始？这种选择对算法效率有何影响？
▷