LeetCode 补充题 135. 轴对齐矩形的公共交集
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 223. 矩形面积
:::
给你若干个轴对齐矩形
rectangles。每个矩形用[x1, y1, x2, y2]表示，其中(x1, y1)是左下角，(x2, y2)是右上角。请返回所有矩形公共交集的矩形坐标。如果不存在公共区域，或公共区域的面积为
0，返回空数组。
示例 1：
输入：
rectangles = [[0,0,5,5],[2,1,6,4],[1,2,4,6]]
输出：[2,2,4,4]
解释： 共同区域的左下角取各左下坐标的最大值，右上角取最小值。
示例 2：
输入：
rectangles = [[0,0,1,1],[1,0,2,1]]
输出：[]
解释： 两个矩形仅接触边界，共同面积为 0。
提示：
- 输入至少一个矩形，且
x1<x2、y1<y2。 - 坐标为整数。
- 返回坐标，不计算矩形并集或仅两两重叠的区域。
题意分析
一个点同时落在所有矩形内，要求它的横坐标满足所有横向区间约束，纵坐标也满足所有纵向区间约束。矩形轴对齐使这两个方向独立，可以分别求一维交集再组合。
解法：分别取横纵坐标交集
核心思路
[!blue]
公共左边界必须不小于任意矩形的左边界，所以取最大值；公共右边界不能大于任意右边界，所以取最小值。下边界取最大，上边界取最小，处理每个矩形后，四个值就描述已处理矩形的公共约束。
用第一块矩形的副本初始化，避免假定坐标为正或改写输入。全部扫描后，仅当
left < right且bottom < top时返回坐标；相等表示只接触一条线或一个点，面积为 0，应返回空数组。只比较坐标即可，无需计算面积，既满足返回坐标的要求，也避免无必要的宽高乘法溢出。
解题步骤
- 用第一块矩形初始化四条边界。
- 不断取更大的左下边界、更小的右上边界。
- 若任一方向宽度非正则返回空，否则返回公共矩形。
代码实现
class Solution {
public int[] intersection(int[][] rectangles) {
int[] out = rectangles[0].clone();
for (int[] r : rectangles) {
out[0] = Math.max(out[0], r[0]);
out[1] = Math.max(out[1], r[1]);
out[2] = Math.min(out[2], r[2]);
out[3] = Math.min(out[3], r[3]);
}
return out[0] < out[2] && out[1] < out[3] ? out : new int[0];
}
}
func intersection(rectangles [][]int) []int {
out := append([]int(nil), rectangles[0]...)
for _, r := range rectangles {
out[0] = max(out[0], r[0])
out[1] = max(out[1], r[1])
out[2] = min(out[2], r[2])
out[3] = min(out[3], r[3])
}
if out[0] >= out[2] || out[1] >= out[3] {
return []int{}
}
return out
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(1)$。
关键点总结
[!green]
二维轴对齐矩形的交集可拆成两个一维区间交集，不能推广为任意多边形只取包围盒。
易错点总结
[!yellow]
一般多边形的交集不一定是矩形；这里的矩形特例不能冒充任意多边形算法。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 986. 区间列表的交集 | 中等 | 同样取一维区间交集，本题分别在横轴与纵轴累计所有矩形的公共范围。 |
| 223. 矩形面积 | 中等 | 原题求两矩形覆盖总面积，本题只求全部矩形的共同部分，边界接触没有正面积。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！