LeetCode 836. 矩形重叠
目录
题目描述
题意分析
给两个轴对齐的矩形，各用
[x1, y1, x2, y2]描述，前两个数是左下角坐标，后两个数是右上角坐标。判断它们是否重叠。题目对「重叠」给了非常明确的定义：两个矩形的相交部分必须有正面积。这是最关键的约束信号——只是贴着一条边、或者只在一个角上碰到一个点，交集的面积是 0，都不算重叠。
「轴对齐」是另一个重要信号。它意味着矩形的四条边分别平行于 x 轴和 y 轴，于是矩形可以拆成两个方向上的区间乘积：x 方向的区间
[x1, x2]和 y 方向的区间[y1, y2]。如果矩形可以任意旋转，这题就完全是另一个难度了。题目还保证
x1 < x2且y1 < y2（或者在退化输入里允许相等，此时矩形本身面积为 0），所以不需要担心坐标顺序颠倒。边界情况包括：两个矩形共享一条边；只共享一个角点；一个矩形完全包含另一个；两个矩形完全分离；以及某个矩形本身就是退化的线段或点。
解法：判断两个坐标轴上的投影
核心思路
轴对齐矩形可以看成一个 x 区间与一个 y 区间的笛卡尔积。两个矩形有正面积交集，当且仅当它们在 x、y 两个方向上的投影都存在正长度交集。
对一维区间
[a1, a2]和[b1, b2]，正长度相交等价于：
a1 < b2 && b1 < a2这比枚举“不重叠的左、右、上、下”更直接，也天然覆盖包含与交叉。比较必须严格：端点相等只代表贴边，交集宽度或高度为 0。
正确性来自二维面积公式：交集宽度为
min(x2) - max(x1)，交集高度同理；只有两者都大于 0，乘积才大于 0。代码中的四个严格不等式正好分别表达这两个条件。
解题步骤
- 判断 x 投影是否正长度相交：
rec1[0] < rec2[2] && rec2[0] < rec1[2]。- 判断 y 投影是否正长度相交：
rec1[1] < rec2[3] && rec2[1] < rec1[3]。- 两个方向同时相交才返回
true。例如
[0,0,2,2]与[1,1,3,3]的两个投影都重叠，交集是[1,1,2,2]。而[0,0,1,1]与[1,0,2,1]在 x 方向只有端点相接，所以返回false。
代码实现
class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
return rec1[0] < rec2[2]
&& rec2[0] < rec1[2]
&& rec1[1] < rec2[3]
&& rec2[1] < rec1[3];
}
}
func isRectangleOverlap(rec1 []int, rec2 []int) bool {
return rec1[0] < rec2[2] &&
rec2[0] < rec1[2] &&
rec1[1] < rec2[3] &&
rec2[1] < rec1[3]
}
复杂度分析
- 时间复杂度：$O(1)$，只做固定次数的坐标比较。
- 空间复杂度：$O(1)$。
关键点总结
- 二维矩形相交可降维为两个一维区间同时相交。
- 正面积要求两个方向的交集长度都严格大于 0。
- 包含、部分重叠和十字交叉都被同一组条件覆盖，无需分类讨论。
- 面试若追问交集面积，可分别求
max(0, min(right) - max(left))后相乘。
易错点总结
- 把
<写成<=，会把共边或共点误判为正面积重叠。- 只判断某个角点是否落入另一矩形，会漏掉十字交叉。
- 只检查 x 方向，无法排除上下分离的矩形。
- 坐标顺序是
[x1, y1, x2, y2]，y 方向应使用下标 1 和 3。- 若改用面积公式，每个方向都要先把负长度截为 0，不能只判断乘积非零。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 223. 矩形面积 | 中等 | 计算重叠面积 |
| 391. 完美矩形 | 困难 | 面积求和与角点抵消 |
| 56. 合并区间 | 中等 | 排序后合并区间 |
| 435. 无重叠区间 | 中等 | 贪心删除最少区间 |
| 252. 会议室 | 简单 | 判定是否存在冲突 |
| 253. 会议室 II | 中等 | 求最大同时重叠数 |