这次我们来看力扣LeetCode第836题“矩形重叠”。这道题本身不复杂但它是面试中检验基础几何思维和编码严谨性的高频考点。很多同学一看题目觉得简单上手一写却容易在边界条件上栽跟头。本文将带你用Python彻底拆解这个问题从最直观的解法到最高效的数学判断并深入探讨其背后的算法思想与工程实践价值。对于准备面试或刷题的同学掌握这道题不仅能解决一个具体问题更能提升你处理区间、坐标、边界等问题的通用能力。我们会先明确问题定义然后一步步推导出最优解最后给出完整的代码实现、测试用例以及性能分析。1. 核心能力速览在深入代码之前我们先快速把握这个问题的核心要点和解决方案的规格。能力项说明问题类型计算几何 / 区间判断输入格式两个矩形每个矩形由左下角坐标[x1, y1]和右上角坐标[x2, y2]表示。输出要求布尔值。True表示矩形重叠False表示不重叠。时间复杂度O(1)。无论矩形坐标值多大判断步骤是常数时间。空间复杂度O(1)。只使用了几个临时变量。核心算法投影判断法分离轴定理的简化应用。关键难点正确处理边界情况相切算不算重叠题目通常定义“仅在边或角接触”不算重叠。适合场景面试手撕代码、图形学碰撞检测基础、游戏开发、UI组件布局判断等。2. 问题定义与适用场景2.1 力扣原题描述题目“矩形重叠”要求判断两个轴对齐的矩形是否重叠。轴对齐意味着矩形的边平行于x轴和y轴。 输入是两个长度为4的整数列表rec1和rec2分别代表两个矩形rec1 [x1, y1, x2, y2]rec2 [x3, y3, x4, y4]其中(x1, y1)是矩形1左下角的坐标(x2, y2)是矩形1右上角的坐标。矩形2同理。 题目明确如果两个矩形有重叠的正面积则判定为重叠。这意味着仅在边或角上接触面积为0不算重叠。2.2 为什么这道题重要面试高频考点它考察将几何问题转化为逻辑判断的能力代码虽短但极易写错边界。基础算法思想是“分离轴定理”在二维轴对齐包围盒AABB碰撞检测中的最简形式是游戏物理引擎、图形界面库的底层基础之一。培养严谨性通过分析多种情况完全分离、包含、相交、相切可以极大提升对问题边界条件的考虑周全性。3. 环境准备与思维推导解决算法题环境准备不仅仅是安装Python更重要的是理清解题思路。我们不需要复杂的深度学习框架只需要一个能运行Python的环境和清晰的逻辑。3.1 基础环境Python 3.x任何3.6及以上版本均可。本题不涉及特殊库。代码编辑器或IDEVS Code, PyCharm, 甚至记事本都可以。力扣刷题习惯直接在力扣在线编辑器写或本地创建solution.py文件。3.2 从暴力思维到数学优化最直观的想法是遍历两个矩形区域的所有整数点看是否有公共点。但这种方法效率极低O(n²)且对于非整数坐标或大面积矩形不可行。我们需要一个判断准则两个矩形不重叠的充要条件是什么 反过来想两个矩形重叠的充要条件是它们在x轴和y轴上的投影都重叠。投影到x轴矩形变成线段[x1, x2]和[x3, x4]。两条线段不重叠的条件是一条线段完全在另一条的左边或右边。即x2 x3或x4 x1。投影到y轴同理矩形变成线段[y1, y2]和[y3, y4]。不重叠条件y2 y3或y4 y1。如果在x轴或y轴上任意一个维度不重叠那么两个矩形在二维空间上必定不重叠。反之如果在两个维度上都重叠则矩形重叠。边界条件处理题目要求“正面积”重叠因此当x2 x3右边界等于左边界时它们只是边接触投影长度为0不算重叠。我们的不重叠条件x2 x3使用了正好将这种“相切”情况判定为不重叠。y轴同理。4. 代码实现与逐行解析基于以上推导我们可以写出极其简洁的代码。4.1 标准解法代码class Solution: def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) - bool: # 解构坐标增加可读性 x1, y1, x2, y2 rec1 x3, y3, x4, y4 rec2 # 判断是否重叠x轴投影有重叠 且 y轴投影有重叠 # 不重叠的条件取反即为重叠的条件 overlap_in_x not (x2 x3 or x4 x1) # x轴有重叠 overlap_in_y not (y2 y3 or y4 y1) # y轴有重叠 return overlap_in_x and overlap_in_y代码解析x2 x3矩形1的右边界在矩形2的左边界的左侧或重合即矩形1在矩形2左边。x4 x1矩形2的右边界在矩形1的左边界的左侧或重合即矩形2在矩形1左边。or连接满足其一则说明在x轴上不重叠。not (...)对不重叠条件取反得到“x轴有重叠”的布尔值。对y轴进行完全相同逻辑的判断。最终结果两个维度都有重叠矩形才重叠。4.2 更简洁的写法面试常用很多面试官喜欢看到更紧凑的写法逻辑等价class Solution: def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) - bool: x1, y1, x2, y2 rec1 x3, y3, x4, y4 rec2 # 直接返回重叠条件 return x1 x4 and x3 x2 and y1 y4 and y3 y2解析x1 x4矩形1的左边界 矩形2的右边界。x3 x2矩形2的左边界 矩形1的右边界。同时满足以上两点意味着在x轴上两条线段有正长度的重叠部分不是相切。y轴同理。四个条件同时满足则矩形重叠。两种写法对比第一种逻辑更贴近“不重叠条件取反”的思维过程易于理解和讲解。第二种是第一种的等价化简更简洁。面试时如果先写出第一种再优化成第二种能展示你的思维过程。5. 功能测试与效果验证理论正确不代表代码正确必须用测试用例验证。我们设计几组典型的输入覆盖各种边界情况。5.1 测试用例设计def test_isRectangleOverlap(): solution Solution() # 测试用例1: 明显重叠 rec1 [0, 0, 2, 2] rec2 [1, 1, 3, 3] assert solution.isRectangleOverlap(rec1, rec2) True, “用例1失败” print(“测试用例1明显重叠通过”) # 测试用例2: 完全分离 (x轴分离) rec1 [0, 0, 1, 1] rec2 [2, 0, 3, 1] assert solution.isRectangleOverlap(rec1, rec2) False, “用例2失败” print(“测试用例2x轴分离通过”) # 测试用例3: 完全分离 (y轴分离) rec1 [0, 0, 1, 1] rec2 [0, 2, 1, 3] assert solution.isRectangleOverlap(rec1, rec2) False, “用例3失败” print(“测试用例3y轴分离通过”) # 测试用例4: 包含关系 (一个矩形在另一个内部) rec1 [0, 0, 3, 3] rec2 [1, 1, 2, 2] assert solution.isRectangleOverlap(rec1, rec2) True, “用例4失败” print(“测试用例4包含关系通过”) # 测试用例5: 边接触 (不算重叠) rec1 [0, 0, 1, 1] rec2 [1, 0, 2, 1] # rec1的右边界x1 等于 rec2的左边界x1 assert solution.isRectangleOverlap(rec1, rec2) False, “用例5失败” print(“测试用例5边接触通过”) # 测试用例6: 角接触 (不算重叠) rec1 [0, 0, 1, 1] rec2 [1, 1, 2, 2] # rec1的右上角(1,1) 等于 rec2的左下角(1,1) assert solution.isRectangleOverlap(rec1, rec2) False, “用例6失败” print(“测试用例6角接触通过”) # 测试用例7: 负坐标矩形重叠 rec1 [-5, -5, 0, 0] rec2 [-3, -3, 2, 2] assert solution.isRectangleOverlap(rec1, rec2) True, “用例7失败” print(“测试用例7负坐标重叠通过”) print(“所有测试用例通过”) if __name__ “__main__”: test_isRectangleOverlap()运行这段测试代码如果所有断言通过则证明我们的算法逻辑覆盖了核心场景。5.2 在力扣平台上验证将Solution类代码复制到力扣第836题的编辑器里点击运行或提交。力扣的测试平台包含更多隐藏用例能进一步检验代码的鲁棒性。一次提交通过Accepted是最终的验证标准。6. 算法扩展与接口化思考虽然本题是简单的函数但在实际工程中矩形碰撞检测可能被频繁调用。我们可以从工程角度进行一些扩展思考。6.1 批量矩形对检测假设有一个矩形列表需要找出所有相互重叠的矩形对。暴力两两比较的时间复杂度是 O(n²)但结合空间划分数据结构如四叉树、网格划分可以优化。from typing import List, Tuple def find_all_overlaps(rectangles: List[List[int]]) - List[Tuple[int, int]]: “”“找出所有重叠的矩形对索引”“” n len(rectangles) overlaps [] for i in range(n): for j in range(i 1, n): if is_overlap(rectangles[i], rectangles[j]): overlaps.append((i, j)) return overlaps def is_overlap(rec1, rec2): “”“复用我们的核心判断逻辑”“” x1, y1, x2, y2 rec1 x3, y3, x4, y4 rec2 return x1 x4 and x3 x2 and y1 y4 and y3 y2 # 示例使用 rects [ [0, 0, 2, 2], [1, 1, 3, 3], [5, 5, 6, 6], [0, 3, 2, 5] ] print(find_all_overlaps(rects)) # 输出[(0, 1)] 只有第0个和第1个矩形重叠6.2 计算重叠区域面积如果题目升级为“计算重叠矩形的面积”我们可以在判断重叠的基础上进一步计算。def overlap_area(rec1: List[int], rec2: List[int]) - int: “”“计算两个矩形的重叠面积如果不重叠则返回0”“” x1, y1, x2, y2 rec1 x3, y3, x4, y4 rec2 # 判断是否重叠 if not (x1 x4 and x3 x2 and y1 y4 and y3 y2): return 0 # 计算重叠部分在x轴和y轴上的长度 overlap_width min(x2, x4) - max(x1, x3) overlap_height min(y2, y4) - max(y1, y3) return overlap_width * overlap_height # 测试 rec1 [0, 0, 3, 3] rec2 [1, 1, 4, 4] print(overlap_area(rec1, rec2)) # 输出4 (重叠区域为2x2的正方形)7. 性能分析与资源占用对于单次判断本题算法是常数时间复杂度和常数空间复杂度性能无可挑剔。但理解其性能特征对处理大规模数据仍有意义。时间复杂度 O(1)无论坐标值多大只进行有限次约6-8次整数比较和布尔运算。空间复杂度 O(1)只使用了固定数量的局部变量存储坐标。CPU/内存占用可忽略不计。即使在每秒百万次调用的场景如游戏物理引擎这也是最优选择之一。与暴力法的对比假设矩形平均边长为L暴力遍历像素点法复杂度为O(L²)而本方法为O(1)效率有云泥之别。工程建议在需要高频调用的系统中确保矩形坐标数据以紧凑的方式如数组或结构体存储避免在函数调用时产生不必要的对象构造开销。对于Python直接传递列表或元组是高效的。8. 常见错误与排查方法即使思路正确实现时也容易踩坑。下表总结了常见错误及解决方法。问题现象可能原因排查方式解决方案边接触或角接触被判定为重叠使用了错误的比较运算符如误写为。用测试用例5和6验证。确认题目要求。若“相切不算重叠”则判断条件必须用x1 x4 and x3 x2严格小于。包含关系被判定为不重叠逻辑写反了将“重叠条件”误写为“不重叠条件”。用测试用例4验证。回顾逻辑重叠条件是“两个维度都重叠”而不是“任一维度不重叠”。坐标顺序假设错误假设输入一定是[左下x, 左下y, 右上x, 右上y]但实际输入可能顺序混乱。阅读题目约束。力扣本题明确左下和右上坐标且x1 x2,y1 y2。信任题目约束。如果约束不存在需先对坐标排序left min(x1, x2),right max(x1, x2)。处理浮点数坐标时出错算法直接用于浮点数由于精度问题导致边界判断失误。检查输入是否为浮点型。引入一个小的误差容忍度epsilon例如if x1 eps x4 and x3 eps x2 ...。函数返回类型错误返回了0/1或字符串而不是布尔值True/False。检查力扣错误信息或本地测试。确保函数返回bool类型。最易错点混淆“重叠”与“不重叠”的条件。一个可靠的记忆方法是“如果矩形A完全在矩形B的左边、右边、上边或下边则它们不重叠”。代码中检查这四个方向如果都不满足则重叠。9. 最佳实践与刷题建议9.1 对于本题的实践理解优先于记忆不要死记return x1 x4 and x3 x2 and y1 y4 and y3 y2这行代码。要理解其背后的投影思想这样即使遇到三维盒子碰撞也能类推。画图辅助在纸上或使用绘图工具画出矩形分离、相交、包含、相切等多种情况直观理解不等式条件。测试驱动像第5节那样先写出全面的测试用例再编写代码确保覆盖所有边界。尝试变种题做完本题可以尝试力扣223题“矩形面积”它需要先判断重叠再计算总面积是本题的自然延伸。9.2 通用刷题策略明确问题与约束仔细读题明确输入输出格式、边界条件相切算不算坐标是否整数。从简单方法思考先想最直观可能低效的方法确保理解问题本质。寻找优化模式识别无效操作寻找数学规律或数据结构进行优化。本题的优化就是从“遍历点”到“判断投影”。代码简洁清晰使用有意义的变量名适当添加注释。面试时清晰的逻辑比一行炫技的代码更重要。总结归类将本题归类到“计算几何”、“区间判断”等知识树下建立自己的解题图谱。10. 总结与下一步力扣836题“矩形重叠”是一个经典的入门级几何问题。它的价值不在于算法本身多么高深而在于训练我们将空间问题分解为维度投影的思维模式以及编写严谨、无懈可击的边界判断代码的能力。最值得掌握的点核心判断条件overlap (x1 x4) and (x3 x2) and (y1 y4) and (y3 y2)。务必理解每个不等式的几何意义。边界处理明确题目对“相切”的定义选用或。思维方法将二维重叠问题转化为两个一维区间重叠问题的组合。最容易踩的坑把条件写反或者错误处理坐标大小关系。下一步可以做什么挑战升级解决力扣223题“矩形面积”计算两个矩形覆盖的总面积。扩展维度思考如何判断三维空间中轴对齐长方体的重叠。深入应用了解该算法在游戏开发碰撞检测、图形用户界面组件布局、数据库空间索引中的实际应用。把这个简单的算法吃透下次面试官再问到矩形或区间相关的问题你就能从容应对了。建议将代码和测试用例保存到你的刷题笔记中随时复习。