LeetCode 836. 矩形重叠

约 3 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 腾讯 字节 阿里 华为 虾皮
标签
数学 几何

题目描述

✅ 836. 矩形重叠

image-20260928223244593

image-20260928223244594

题意分析

每个矩形由 [x1, y1, x2, y2] 表示，前两个坐标是左下角，后两个是右上角；矩形边与坐标轴平行，题目保证矩形自身面积为正。

要判断两个矩形是否拥有正面积的公共区域。只接触一条边或一个角点时，交集面积为零，应返回 false；一方包含另一方也属于重叠。

解法：判断两个坐标轴上的投影

核心思路

[!blue]

轴对齐矩形是横坐标区间与纵坐标区间的组合。两矩形的公共区域，也就是它们横向交集与纵向交集的组合；只有两个方向都重叠出正长度，组合起来才会有正面积。

对两个一维有效区间，只有两种不产生正长度交集的情况：第一个完全在第二个左边，或者第二个完全在第一个左边，端点相等的接触也包括在内。排除这两种情况，就得到“第一个左端严格小于第二个右端，并且第二个左端严格小于第一个右端”。

在横轴上，这两个条件是 rec1[0] < rec2[2] 和 rec2[0] < rec1[2]；纵轴上用下标 1、3 做同样比较。四个条件全部成立，才返回重叠。

这个判断直接覆盖部分交叉、完全包含及边角接触，不需要枚举相对位置。也不需要计算面积：坐标只做大小比较，避免为了布尔结果引入乘法或处理负的交集长度。

解题步骤

  1. 比较两个矩形的左右边界，确认横向投影有正长度交集。
  2. 比较上下边界，确认纵向投影也有正长度交集。
  3. 两个方向的条件用逻辑与连接，作为最终答案。

代码实现

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)$，没有额外存储。

关键点总结

[!green]

  • 二维正面积交集等价于两个一维投影都具有正长度交集。
  • 使用严格小于，等号意味着该方向只有接触，没有长度。
  • 直接排除左右分离、上下分离即可统一覆盖全部位置关系。

易错点总结

[!yellow]

  • 把 < 改成 <=，会把共边或共点误判成正面积重叠。
  • 两个方向必须同时满足，使用逻辑或会把只在一个投影上相交的矩形判成重叠。
  • 不能只检查某个角点是否落入另一矩形，十字交叉时可能没有角点落入，但仍有公共面积。
  • 输入顺序是 [x1, y1, x2, y2]，横向使用下标 0、2，纵向使用 1、3。

相似题目

题目 难度 关联与区别
223. 矩形面积 中等 正面积交集的边界判定相同，原题还用交集面积计算两个矩形的并集面积。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/98665301
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！