在算法面试和日常刷题中判断两个矩形是否重叠是一个经典且高频的几何问题。它不仅是力扣LeetCode第836题的原题更是许多图形学、游戏开发、UI碰撞检测等实际场景中的基础操作。很多开发者在初次接触时容易陷入复杂的边界条件判断导致代码冗长且易错。本文将彻底拆解这个问题从问题本质、数学原理出发用Python给出清晰、高效的多种解法并深入探讨其变种与工程实践中的应用。无论你是正在准备面试的求职者还是希望巩固算法基础的开发者都能从中获得一套可直接复用的解题框架和避坑指南。1. 问题背景与核心概念1.1 问题描述LeetCode 836. 矩形重叠题目给出两个轴对齐的矩形。轴对齐意味着矩形的边平行于坐标系的X轴和Y轴。每个矩形通过其左下角坐标(x1, y1)和右上角坐标(x2, y2)来定义。我们需要编写一个函数判断这两个矩形是否有重叠的区域面积为正的重叠。函数签名Python:def isRectangleOverlap(rec1: List[int], rec2: List[int]) - bool:输入rec1 [x1, y1, x2, y2]rec2 [x3, y3, x4, y4]输出如果重叠返回True。如果不重叠返回False。示例 1:输入rec1 [0,0,2,2], rec2 [1,1,3,3] 输出true示例 2:输入rec1 [0,0,1,1], rec2 [1,0,2,1] 输出false注意在示例2中矩形只是边相邻没有正面积的重叠因此返回false。1.2 为什么这个问题重要理解矩形重叠判断其意义远超一道算法题面试高频考点它考察了对问题建模、边界条件处理以及空间想象能力。计算机图形学基础是碰撞检测如游戏中的物体碰撞、窗口管理如操作系统中的窗口重叠、图形裁剪等技术的基石。空间数据处理在地理信息系统GIS、数据库空间索引如R-tree中快速判断两个空间对象是否相交是核心操作。算法思维的训练它将一个二维空间问题巧妙地分解为两个独立的一维区间问题是“降维”思想的典型应用。1.3 关键概念投影与分离轴定理判断两个轴对齐矩形是否重叠其核心思想来源于分离轴定理的一个特例。简单来说如果两个矩形在X轴和Y轴上的投影区间都分别有重叠那么它们在二维平面上就一定有重叠。反之如果存在一条轴X轴或Y轴使得它们的投影区间不重叠那么这两个矩形就是分离的。这让我们可以将复杂的二维重叠判断简化为两个一维区间是否重叠的判断。这是解决本问题的钥匙。2. 环境准备与解题思路2.1 解题环境对于LeetCode刷题我们通常只需要一个在线的编程环境或本地的Python解释器。本文所有代码均基于Python 3编写不依赖任何第三方库。本地环境建议Python 3.6确保有基本的运行环境。代码编辑器/IDE如VS Code、PyCharm或任何你熟悉的文本编辑器。LeetCode刷题插件可选许多编辑器有插件可以方便地运行和测试样例。2.2 核心思路拆解让我们将思路可视化。假设有两个矩形A和B。在X轴上矩形A占据区间[A.x1, A.x2]矩形B占据区间[B.x1, B.x2]。在Y轴上矩形A占据区间[A.y1, A.y2]矩形B占据区间[B.y1, B.y2]。重叠的条件是在X轴上区间[A.x1, A.x2]和区间[B.x1, B.x2]有交集。在Y轴上区间[A.y1, A.y2]和区间[B.y1, B.y2]有交集。不重叠的条件更容易判断只要满足以下任意一条两个矩形就不重叠矩形A整体在矩形B的右侧A.x1 B.x2矩形A整体在矩形B的左侧A.x2 B.x1矩形A整体在矩形B的上方A.y1 B.y2矩形A整体在矩形B的下方A.y2 B.y1这四种情况涵盖了所有不重叠的可能性包括相邻但不重叠的情况。因此我们只需要检查是否不满足这四条中的任何一条即可得出重叠的结论。3. 方法一检查区域法正向思维这是最直观的方法。如果两个矩形重叠那么重叠部分的矩形其左下角坐标(x_overlap, y_overlap)和右上角坐标(x2_overlap, y2_overlap)应该满足x_overlap max(rec1[0], rec2[0])重叠部分左边界取两个矩形左边界的最大值y_overlap max(rec1[1], rec2[1])重叠部分下边界取两个矩形下边界的最大值x2_overlap min(rec1[2], rec2[2])重叠部分右边界取两个矩形右边界的最小值y2_overlap min(rec1[3], rec2[3])重叠部分上边界取两个矩形上边界的最小值然后判断这个“重叠矩形”是否有效即宽度和高度是否都为正数。from typing import List def isRectangleOverlap_area(rec1: List[int], rec2: List[int]) - bool: 方法一通过计算潜在重叠区域判断 # 计算重叠矩形的左、下、右、上边界 left max(rec1[0], rec2[0]) bottom max(rec1[1], rec2[1]) right min(rec1[2], rec2[2]) top min(rec1[3], rec2[3]) # 如果右边界 左边界 且 上边界 下边界则重叠区域有效面积为正 return right left and top bottom # 测试用例 if __name__ __main__: test_cases [ ([0,0,2,2], [1,1,3,3], True), # 重叠 ([0,0,1,1], [1,0,2,1], False), # 相邻不重叠 ([0,0,1,1], [2,2,3,3], False), # 完全分离 ([0,0,3,3], [1,1,2,2], True), # 包含 ] for rec1, rec2, expected in test_cases: result isRectangleOverlap_area(rec1, rec2) print(frec1{rec1}, rec2{rec2}, 预期{expected}, 结果{result}, {通过 if result expected else 失败})运行结果rec1[0, 0, 2, 2], rec2[1, 1, 3, 3], 预期True, 结果True, 通过 rec1[0, 0, 1, 1], rec2[1, 0, 2, 1], 预期False, 结果False, 通过 rec1[0, 0, 1, 1], rec2[2, 2, 3, 3], 预期False, 结果False, 通过 rec1[0, 0, 3, 3], rec2[1, 1, 2, 2], 预期True, 结果True, 通过方法优点思路非常直观符合人类的空间思维。代码简洁易于理解和记忆。可以轻松扩展为计算重叠面积或重叠矩形坐标。4. 方法二检查分离法逆向思维根据2.2中的不重叠条件我们可以先判断矩形是否不重叠。如果所有不重叠的条件都不满足那么它们就是重叠的。from typing import List def isRectangleOverlap_separate(rec1: List[int], rec2: List[int]) - bool: 方法二通过检查是否分离来判断 # 检查四种不重叠的情况 # 1. rec1 在 rec2 左侧 # 2. rec1 在 rec2 右侧 # 3. rec1 在 rec2 下方 # 4. rec1 在 rec2 上方 # 如果以上任意一种情况成立则两个矩形不重叠。 # 因此重叠的条件是“以上所有情况都不成立”。 not_overlap (rec1[2] rec2[0] or # rec1在rec2左侧 rec1[0] rec2[2] or # rec1在rec2右侧 rec1[3] rec2[1] or # rec1在rec2下方 rec1[1] rec2[3]) # rec1在rec2上方 return not not_overlap # 使用相同的测试用例进行验证 if __name__ __main__: test_cases [ ([0,0,2,2], [1,1,3,3], True), ([0,0,1,1], [1,0,2,1], False), ([0,0,1,1], [2,2,3,3], False), ([0,0,3,3], [1,1,2,2], True), ] for rec1, rec2, expected in test_cases: result isRectangleOverlap_separate(rec1, rec2) print(frec1{rec1}, rec2{rec2}, 预期{expected}, 结果{result}, {通过 if result expected else 失败})运行结果与方法一一致。方法优点逻辑清晰直接对应“分离”的四种几何位置关系。在某些情况下如早期判断出分离可能提前返回但在此简单实现中差异不大。是分离轴定理思想的直接代码体现。5. 方法三区间投影法降维思想这是对方法一的另一种表述更强调“投影”和“区间重叠”的概念。我们将二维重叠问题分解为两个一维区间重叠问题。from typing import List def isRectangleOverlap_interval(rec1: List[int], rec2: List[int]) - bool: 方法三投影到X轴和Y轴判断区间是否重叠 def intervals_overlap(start1, end1, start2, end2): 判断两个一维区间 [start1, end1] 和 [start2, end2] 是否重叠端点不重合 # 区间重叠的条件是第一个区间的起点小于第二个区间的终点 # 并且第二个区间的起点小于第一个区间的终点。 return start1 end2 and start2 end1 # 判断X轴投影区间是否重叠 overlap_x intervals_overlap(rec1[0], rec1[2], rec2[0], rec2[2]) # 判断Y轴投影区间是否重叠 overlap_y intervals_overlap(rec1[1], rec1[3], rec2[1], rec2[3]) # 两个方向都重叠则矩形重叠 return overlap_x and overlap_y # 测试验证 if __name__ __main__: test_cases [ ([0,0,2,2], [1,1,3,3], True), ([0,0,1,1], [1,0,2,1], False), ([0,0,1,1], [2,2,3,3], False), ([0,0,3,3], [1,1,2,2], True), ] for rec1, rec2, expected in test_cases: result isRectangleOverlap_interval(rec1, rec2) print(frec1{rec1}, rec2{rec2}, 预期{expected}, 结果{result}, {通过 if result expected else 失败})方法优点模块化清晰将核心逻辑intervals_overlap独立出来可复用性高。完美体现了“降维”的算法思想有助于理解更复杂的几何碰撞检测问题。条件判断start1 end2 and start2 end1是判断开区间重叠的经典写法。6. 边界条件与常见错误分析这是本题最容易出错的地方。很多开发者写的代码在大部分情况下正确但遇到边界情况就出错。6.1 关键如何定义“重叠”题目要求的是有正面积的重叠。这意味着边重合不算重叠例如rec1[0,0,1,1], rec2[1,0,2,1]它们在X轴上点x1处重合但重合的是一条线面积为0因此返回False。点重合不算重叠例如rec1[0,0,1,1], rec2[1,1,2,2]它们在点(1,1)处接触面积也为0返回False。6.2 错误写法示例错误写法1使用或判断重叠区域# 错误代码 def isRectangleOverlap_wrong1(rec1, rec2): left max(rec1[0], rec2[0]) right min(rec1[2], rec2[2]) bottom max(rec1[1], rec2[1]) top min(rec1[3], rec2[3]) # 错误如果矩形只是边或点接触这里会返回True return right left and top bottom这个函数对于“相邻”的矩形会错误地返回True因为它允许宽度或高度为0。错误写法2混淆坐标顺序题目明确约定输入是[x1, y1, x2, y2]且x1 x2,y1 y2。但如果你在解题时自己定义变量可能会不小心写反。# 易混淆的代码 x1, y1, x2, y2 rec1 x3, y3, x4, y4 rec2 # 务必确保 x1x2, y1y2题目输入已保证但自己处理数据时要小心。6.3 边界测试用例集一个健壮的解决方案应该能通过以下所有测试test_suite [ # (rec1, rec2, expected_result, description) ([0,0,2,2], [1,1,3,3], True, 典型重叠), ([0,0,1,1], [1,0,2,1], False, 右边相邻X轴边重合), ([0,0,1,1], [0,1,1,2], False, 上边相邻Y轴边重合), ([0,0,1,1], [1,1,2,2], False, 右上角点接触), ([0,0,1,1], [2,2,3,3], False, 完全分离), ([0,0,3,3], [1,1,2,2], True, 完全包含), ([1,1,2,2], [0,0,3,3], True, 被完全包含), ([0,0,2,2], [0,0,2,2], True, 完全相同重叠面积即自身), ([0,0,0,0], [0,0,0,0], False, 退化矩形点根据正面积定义不重叠), ]建议你在编写完代码后用这个测试集跑一遍。7. 性能分析与算法拓展7.1 时间复杂度与空间复杂度时间复杂度以上三种方法都只进行了有限次4-6次比较和算术运算因此时间复杂度是O(1)。空间复杂度只使用了常数个额外变量空间复杂度是O(1)。 对于单个矩形对判断这已经是理论上的最优解。7.2 扩展到N个矩形如果问题变为“判断一组矩形中是否存在任意两个重叠”这就是一个典型的区间重叠检测问题在二维的推广。暴力法两两比较时间复杂度 O(N²)适用于N较小的情况。扫描线算法可以将矩形投影到X轴使用扫描线事件矩形的左边界和右边界配合一个有序数据结构如平衡二叉搜索树来管理当前扫描线穿过的矩形在Y轴上的投影区间从而在 O(N log N) 时间内找出所有重叠的矩形对。这是解决大规模矩形重叠检测的经典方法。7.3 扩展到非轴对齐矩形旋转矩形对于边不与坐标轴平行的矩形判断重叠会复杂得多。此时分离轴定理Separating Axis Theorem, SAT就派上用场了。你需要检查两个矩形在所有可能的方向通常是各自两条边的法线方向共4条轴上的投影是否都有重叠。如果存在一条轴使得投影不重叠则两个矩形分离。这需要向量运算知识。8. 工程实践与最佳实践8.1 代码可读性与防御性编程使用有意义的变量名在工程代码中避免使用rec1[0]而是解构并命名。def is_rectangle_overlap(rec1, rec2): ax1, ay1, ax2, ay2 rec1 # Rectangle A bx1, by1, bx2, by2 rec2 # Rectangle B overlap_x max(ax1, bx1) min(ax2, bx2) overlap_y max(ay1, by1) min(ay2, by2) return overlap_x and overlap_y添加输入验证虽然LeetCode保证输入有效但在实际工程中应该验证输入是否为长度为4的列表且x1 x2,y1 y2。def validate_rectangle(rec): if not isinstance(rec, (list, tuple)) or len(rec) ! 4: raise ValueError(Rectangle must be a list/tuple of 4 numbers.) x1, y1, x2, y2 rec if x1 x2 or y1 y2: raise ValueError(Invalid rectangle coordinates: x1 must be x2 and y1 must be y2.) return x1, y1, x2, y28.2 在图形界面和游戏开发中的应用在PyGame、Unity或前端Canvas开发中矩形碰撞检测是常态。通常游戏引擎或图形库会提供现成的函数如pygame.Rect.colliderect。理解其背后的原理能帮助你在没有现成函数时自己实现或在性能优化时理解其开销。PyGame示例import pygame # 假设有两个矩形对象 rect1 pygame.Rect(0, 0, 100, 100) # (x, y, width, height) rect2 pygame.Rect(50, 50, 100, 100) if rect1.colliderect(rect2): print(矩形发生碰撞) # 其内部实现逻辑就与我们上面讨论的方法一类似。8.3 在数据库空间查询中的应用在PostGISPostgreSQL的空间扩展或MySQL的空间函数中判断几何图形是否相交ST_Intersects是核心操作。对于矩形或边界框查询数据库会利用R-Tree等空间索引来加速。理解矩形重叠的快速判断有助于你写出更高效的空间查询SQL。PostGIS示例概念性-- 查找与给定矩形POLYGON相交的所有地块 SELECT * FROM land_parcels WHERE ST_Intersects(geom, ST_MakeEnvelope(x1, y1, x2, y2, 4326)); -- ST_MakeEnvelope 创建了一个轴对齐的矩形边界框。9. 举一反三相关LeetCode题目掌握矩形重叠后你可以尝试解决以下类似或进阶题目巩固几何和区间问题的解题能力223. 矩形面积在836题的基础上要求计算两个矩形覆盖的总面积。你需要先判断是否重叠如果重叠则减去重叠部分的面积。497. 非重叠矩形中的随机点需要理解矩形不重叠的含义并在此约束下进行随机采样。850. 矩形面积 II计算一组矩形覆盖的总面积是矩形重叠问题的升级版通常需要扫描线算法。391. 完美矩形判断一组矩形是否精确覆盖了一个大的矩形区域无重叠无空隙。这需要更巧妙的边界和面积计算。一维区间问题如252. 会议室判断区间是否重叠、56. 合并区间等。它们是矩形重叠问题在一维的简化是练习区间操作的好题目。10. 总结与学习建议通过本文的详细拆解我们不仅解决了LeetCode 836题更掌握了一套解决空间几何问题的核心方法论降维。将二维的矩形重叠问题分解为两个一维的区间重叠问题极大地简化了思考和编码的复杂度。核心要点回顾重叠的充要条件两个矩形在X轴和Y轴上的投影区间同时有交集且交集长度大于0。三种等价实现计算重叠区域法max(left1, left2) min(right1, right2) and max(bottom1, bottom2) min(top1, top2)。检查分离条件法判断是否不满足四种分离情况中的任何一种。区间投影法抽象出interval_overlap函数分别判断X和Y方向。关键边界题目要求正面积重叠因此判断时使用严格小于 () 而不是小于等于 ()以排除边或点接触的情况。给刷题者的建议动手实现务必自己将三种方法都编码实现一遍并用第6.3节的边界测试用例验证。画图辅助对于几何问题在纸上或绘图软件上画出矩形的相对位置是理清思路、验证边界条件的最有效方法。理解本质不要满足于AC通过题目。多问为什么理解方法背后的数学原理分离轴定理和算法思想降维。横向扩展主动去寻找和练习相关的题目如第9节所列构建自己的知识网络。这道题的价值在于其简洁问题背后蕴含的普遍思想。当你下次遇到更复杂的形状碰撞、时间区间调度、空间索引查询等问题时不妨回想一下矩形重叠的判断逻辑看看是否能运用“投影”和“区间判断”的思想来化繁为简。