很多人在刷 LeetCode 时看到“矩形重叠”这种题目第一反应往往是“这不就是简单的几何判断吗直接比较坐标不就行了” 然后兴冲冲地写下一堆if-else结果要么漏掉边界情况要么代码冗长到难以维护最后在提交时才发现各种意想不到的测试用例。力扣第 836 题“矩形重叠”就是这样一个典型的“简单题陷阱”。它表面上考察的是基础的二维几何知识但真正要你掌握的是一种降维打击的思维模型。如果你还在用“矩形A的四个角是否在矩形B内”这种思路去解题那么这篇文章就是为你准备的。本文将带你跳出直觉陷阱用最简洁、最优雅的 Python 数学逻辑一击即中问题的核心。读完本文你不仅能轻松解决这道题更能学会一种处理区间重叠类问题的通用方法论这在处理日程冲突、资源分配、碰撞检测等实际问题时将让你事半功倍。1. 这篇文章真正要解决的问题我们首先要破除一个迷思LeetCode 上的“简单”题真的简单吗对于第 836 题其“简单”的标签往往让人轻视导致陷入复杂的条件分支判断。实际上这道题的核心价值在于它强迫你从更高维度去抽象问题。真正的问题如何用最少的条件、最低的时间复杂度O(1)和空间复杂度O(1)判断两个轴对齐矩形即边平行于坐标轴的矩形是否重叠。为什么传统思路会失败条件冗余检查一个矩形的角点是否在另一个矩形内部需要检查4个点每个点需要2个条件x和y坐标范围逻辑繁琐。边界情况复杂当矩形只是边接触比如共享一条边时题目通常定义为“不重叠”。如何精确排除这种“相切”情况需要非常小心的不等号处理用还是。代码可读性差一堆嵌套的if语句不仅容易写错几个月后自己都看不懂。本文将解决的正是如何绕过这些坑直接抵达问题的数学本质两个矩形不重叠的充要条件是什么一旦想通了这一点代码将变得异常简洁。这篇文章适合所有正在刷题、希望提升算法思维和代码简洁性的开发者尤其是那些被各种边界条件折磨过的朋友。2. 基础概念与核心原理在深入代码之前我们必须清晰定义问题中的几个关键概念这是写出健壮代码的基础。2.1 矩形在坐标系中的表示在LeetCode本题中一个矩形使用一个长度为4的整数列表[x1, y1, x2, y2]表示。(x1, y1)是其左下角的坐标。(x2, y2)是其右上角的坐标。这是一个轴对齐矩形其四条边分别平行于x轴和y轴。保证x1 x2且y1 y2。例如矩形rec1 [0, 0, 2, 3]表示一个左下角在原点宽为2高为3的矩形。2.2 矩形“重叠”的定义题目要求如果两个矩形有正面积的公共区域则称它们重叠。这意味着仅边或角接触不算重叠。例如一个矩形在另一个矩形的正上方且底边接触不算重叠。必须有共同的内部点。2.3 核心原理投影与分离轴定理的简化版这是本文的核心判断。对于轴对齐矩形判断是否重叠有一个极其高效的方法分别检查它们在x轴和y轴上的投影区间是否都重叠。我们可以将二维的矩形重叠问题分解为两个一维的区间重叠问题X轴投影矩形在x轴上的投影是一个区间[x1, x2]。Y轴投影矩形在y轴上的投影是一个区间[y1, y2]。关键结论两个矩形重叠的充要条件是它们在x轴上的投影区间并且在y轴上的投影区间同时重叠。反之两个矩形不重叠的充要条件是它们在x轴上的投影区间或者在y轴上的投影区间不重叠。这个原理是解决本题的钥匙它将一个二维空间的关系判断简化为了两个独立的一维区间判断复杂度大大降低。3. 环境准备与前置条件解决这道题几乎不需要特殊环境但为了完整性和后续扩展我们明确一下基础环境编程语言Python 3.x。本文所有代码示例均基于Python 3.6。开发工具任何文本编辑器或IDE均可如VSCode、PyCharm、甚至LeetCode在线编辑器。无需额外库本题仅使用Python内置语法和运算符无需安装任何第三方库。核心技能理解列表索引、逻辑运算符and,or,not和比较运算符,,。重点提醒在编写判断逻辑时请特别注意边界条件。题目要求“正面积”重叠因此当区间“恰好相接”时即一个区间的右端点等于另一个区间的左端点应视为不重叠。这决定了我们使用和而不是和。4. 核心流程拆解让我们把“判断投影区间是否重叠”这个核心思想拆解成可执行的步骤。4.1 步骤一提取投影区间对于矩形rec [x1, y1, x2, y2]其X轴投影区间为[x1, x2]。其Y轴投影区间为[y1, y2]。我们需要处理两个矩形rec1和rec2。4.2 步骤二判断一维区间是否重叠核心中的核心如何判断两个一维区间[A_left, A_right]和[B_left, B_right]是否重叠有公共长度重叠的条件是A_left B_right并且B_left A_right。 你可以这样理解区间A的左端点在区间B的右端点左边同时区间B的左端点也在区间A的右端点左边。这样两个区间必然有交集。不重叠的条件分离A_left B_right或者B_left A_right。 即区间A整体在区间B的右边或者区间B整体在区间A的右边。4.3 步骤三应用二维判断将步骤二应用于x轴和y轴X轴重叠条件rec1[x1] rec2[x2]且rec2[x1] rec1[x2]。Y轴重叠条件rec1[y1] rec2[y2]且rec2[y1] rec1[y2]。4.4 步骤四得出最终结论两个矩形重叠的最终条件是X轴条件满足 并且 Y轴条件满足。 用代码表示就是x_overlap and y_overlap。整个思考流程如下图所示逻辑关系问题二维矩形是否重叠降维分解为X轴和Y轴两个一维区间是否重叠判断一维区间是否满足left_A right_B and left_B right_A综合两个维度的判断结果取逻辑与and。5. 完整示例与代码实现理解了原理代码实现就水到渠成。我们将从最直观的写法开始逐步优化到最简洁优雅的形式。5.1 版本一清晰易懂版这个版本将每一步逻辑都清晰展示非常适合理解。def isRectangleOverlap(rec1, rec2): 判断两个轴对齐矩形是否重叠。 :type rec1: List[int] :type rec2: List[int] :rtype: bool # 解包矩形坐标增加可读性 rec1_x1, rec1_y1, rec1_x2, rec1_y2 rec1 rec2_x1, rec2_y1, rec2_x2, rec2_y2 rec2 # 判断在x轴上的投影是否重叠 # 重叠条件rec1的左边界 rec2的右边界 且 rec2的左边界 rec1的右边界 x_overlap rec1_x1 rec2_x2 and rec2_x1 rec1_x2 # 判断在y轴上的投影是否重叠 # 重叠条件rec1的下边界 rec2的上边界 且 rec2的下边界 rec1的上边界 y_overlap rec1_y1 rec2_y2 and rec2_y1 rec1_y2 # 两个方向都重叠矩形才重叠 return x_overlap and y_overlap # 测试用例 if __name__ __main__: # 用例1重叠 rec1 [0, 0, 2, 2] rec2 [1, 1, 3, 3] print(f矩形{rec1}和{rec2}是否重叠 {isRectangleOverlap(rec1, rec2)}) # 应输出 True # 用例2不重叠x轴分离 rec1 [0, 0, 1, 1] rec2 [2, 0, 3, 1] print(f矩形{rec1}和{rec2}是否重叠 {isRectangleOverlap(rec1, rec2)}) # 应输出 False # 用例3不重叠y轴分离 rec1 [0, 0, 1, 1] rec2 [0, 2, 1, 3] print(f矩形{rec1}和{rec2}是否重叠 {isRectangleOverlap(rec1, rec2)}) # 应输出 False # 用例4边接触应返回False rec1 [0, 0, 1, 1] rec2 [1, 0, 2, 1] print(f矩形{rec1}和{rec2}是否重叠 {isRectangleOverlap(rec1, rec2)}) # 应输出 False代码逻辑解释x_overlap rec1_x1 rec2_x2 and rec2_x1 rec1_x2这是区间重叠判断的直接翻译。注意是严格小于()确保了边接触rec1_x2 rec2_x1时返回False。y_overlap同理。最终返回x_overlap and y_overlap要求两个方向必须同时重叠。5.2 版本二简洁一行版面试常用在理解原理后可以写出非常简洁的代码这在面试中能体现你的思维清晰度。def isRectangleOverlap_concise(rec1, rec2): 简洁的一行版本。 核心逻辑判断不重叠的条件然后取反。 # 如果矩形1在矩形2的左侧、右侧、下方、上方则不重叠。 # 注意由于矩形用左下和右上表示‘在左侧’意味着 rec1_x2 rec2_x1 # 我们直接判断重叠的条件即‘不在左侧、不在右侧、不在下方、不在上方’ return not (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上方 # 更Pythonic的写法直接使用投影判断 def isRectangleOverlap_oneline(rec1, rec2): 最经典和优雅的一行版本直接使用投影重叠条件。 return rec1[0] rec2[2] and rec2[0] rec1[2] and rec1[1] rec2[3] and rec2[1] rec1[3]版本对比isRectangleOverlap_concise从“不重叠”的角度思考代码表达了矩形分离的四种情况。逻辑清晰但可读性稍逊。isRectangleOverlap_oneline这是推荐掌握的最优写法。它直接、正面地表达了重叠的四个必要条件没有任何冗余且效率最高。5.3 版本三面向对象版拓展思维如果你在做一个图形项目可以将矩形抽象成类使代码更模块化。class Rectangle: def __init__(self, x1, y1, x2, y2): 初始化矩形确保是有效的轴对齐矩形。 if x1 x2 or y1 y2: raise ValueError(Invalid rectangle coordinates. Must satisfy x1 x2 and y1 y2.) self.x1 x1 self.y1 y1 self.x2 x2 self.y2 y2 def overlaps_with(self, other): 判断当前矩形是否与另一个矩形重叠。 # 使用经典的一行逻辑 return (self.x1 other.x2 and other.x1 self.x2 and self.y1 other.y2 and other.y1 self.y2) staticmethod def from_list(coord_list): 从列表 [x1, y1, x2, y2] 创建矩形对象。 return Rectangle(*coord_list) # 使用示例 if __name__ __main__: rec1_obj Rectangle.from_list([0, 0, 2, 2]) rec2_obj Rectangle.from_list([1, 1, 3, 3]) rec3_obj Rectangle.from_list([5, 5, 6, 6]) print(frec1 与 rec2 重叠: {rec1_obj.overlaps_with(rec2_obj)}) # True print(frec1 与 rec3 重叠: {rec1_obj.overlaps_with(rec3_obj)}) # False这个版本虽然对本题来说“杀鸡用牛刀”但它展示了如何将算法思想封装成可复用的组件在实际工程项目中更有价值。6. 运行结果与效果验证我们使用LeetCode官方的测试用例来验证我们代码的正确性。你可以将isRectangleOverlap_oneline函数直接提交到力扣第836题。如何验证你的代码基础功能测试使用上面代码中的几个简单用例确保能正确区分重叠与不重叠。边界条件测试这是关键。重点测试“边接触”和“角接触”的情况确保返回False。# 测试边界条件 test_cases [ # (rec1, rec2, expected_result, description) ([0,0,1,1], [1,0,2,1], False, 右边接触), ([0,0,1,1], [0,1,1,2], False, 上边接触), ([0,0,1,1], [-1,0,0,1], False, 左边接触), ([0,0,1,1], [0,-1,1,0], False, 下边接触), ([0,0,2,2], [1,1,3,3], True, 部分重叠), ([0,0,1,1], [2,2,3,3], False, 完全分离), ([0,0,3,3], [1,1,2,2], True, 包含), ] for rec1, rec2, expected, desc in test_cases: result isRectangleOverlap_oneline(rec1, rec2) status ✓ if result expected else ✗ print(f{status} {desc}: rec1{rec1}, rec2{rec2}, 预期{expected}, 实际{result})在LeetCode上提交最终极的验证。将函数复制到LeetCode的代码编辑器中点击“执行代码”查看是否通过所有测试用例然后“提交”看是否通过。预期输出 对于上述边界测试你应该看到所有测试用例前都是✓。如果出现✗请仔细检查你的比较运算符必须是和不能是或。7. 常见问题与排查思路即使理解了原理在实现时也可能遇到一些典型问题。下表总结了常见错误和解决方案问题现象可能原因排查方式解决方案边接触的矩形被判断为重叠在判断条件中使用了或检查代码中的比较运算符。题目要求“正面积”重叠边接触不算。将所有判断重叠的条件中的改为。例如rec1_x1 rec2_x2改为rec1_x1 rec2_x2。完全包含的矩形被判断为不重叠逻辑判断顺序错误或使用了“或”逻辑检查最终返回语句。重叠需要X和Y同时满足条件。确保返回语句是return x_cond and y_cond而不是or。索引错误IndexError输入的矩形列表长度不为4在函数开头添加输入验证。添加断言或条件判断assert len(rec1) 4 and len(rec2) 4。代码对某些用例正确对另一些错误坐标赋值错误混淆了x1, y1, x2, y2的顺序使用有意义的变量名解包而不是直接使用rec1[0]。采用x1, y1, x2, y2 rec1的解包方式提高可读性避免索引混淆。认为“一个角在内部”就是重叠理解偏差忽略了矩形可以相交但角点都不在对方内部的情况画图分析。两个矩形十字交叉时可能没有任何一个角点在对方内部但它们确实重叠。回归核心原理必须用投影区间法判断这是唯一可靠的方法。一个高级的思维陷阱有同学会想“先判断不重叠的情况是不是更简单”比如矩形1在矩形2的左边、右边、上边、下边。这思路是对的如我们的简洁版2但必须注意边界。“在左边”的条件是rec1_x2 rec2_x1允许边接触然后对四种分离情况取“或”。最后对整体结果取“非”得到是否重叠。这种“判断不重叠”的思路和“判断重叠”的思路是等价的但更容易在边界条件上出错所以更推荐正面判断的“一行版本”。8. 最佳实践与工程建议将这道题的解决方案融入更广泛的工程和刷题实践中你可以做得更好。8.1 刷题最佳实践先画图再编码对于几何问题在纸上或白板上画出各种情况重叠、分离、包含、边接触直观理解条件。从暴力法思考再优化即使一眼就知道最优解也可以先想想暴力法比如比较所有点这能帮你理清所有边界情况然后再寻找数学规律进行优化。测试用例驱动不要只依赖题目给的例子。自己设计测试用例特别是极端情况坐标很大或很小。边界情况边接触、角接触。对称情况交换两个矩形输入结果应不变。掌握“投影降维”思想这是本题最重要的收获。许多高维问题可以分解为低维问题的组合。例如判断三维长方体是否重叠可以分解为判断x, y, z三个轴上的投影区间是否都重叠。8.2 代码风格与性能追求简洁而非晦涩isRectangleOverlap_oneline版本很简洁但在团队项目中如果算法不是众所周知的建议添加一行注释说明原理如# 检查x轴和y轴投影是否均重叠。时间复杂度与空间复杂度本解法时间和空间复杂度都是 O(1)已是理论最优。无需进一步优化。防御性编程在生产代码中应考虑输入验证。虽然LeetCode保证输入有效但实际工程中需要处理无效矩形如x1 x2或空输入。def isRectangleOverlap_robust(rec1, rec2): # 输入验证 if not rec1 or not rec2 or len(rec1) ! 4 or len(rec2) ! 4: return False # 或抛出异常 # 验证是否为有效矩形左下角坐标小于右上角 if not (rec1[0] rec1[2] and rec1[1] rec1[3] and rec2[0] rec2[2] and rec2[1] rec2[3]): return False # 无效矩形按题目定义可能不会出现但工程中要处理 # 核心逻辑 return rec1[0] rec2[2] and rec2[0] rec1[2] and rec1[1] rec2[3] and rec2[1] rec1[3]8.3 扩展到实际问题“区间重叠”判断是一个基础算法组件应用场景极广日程安排判断两个会议时间段是否冲突。游戏开发2D游戏中精灵的碰撞检测轴对齐包围盒。数据库查询判断两个时间段是否有交集的SQL查询。资源分配检查设备使用时间是否重叠。例如判断两个会议[start1, end1]和[start2, end2]是否冲突的代码与本题的X轴判断逻辑完全一致def is_meeting_conflict(meeting1, meeting2): 判断两个会议时间是否重叠。 start1, end1 meeting1 start2, end2 meeting2 # 会议重叠的条件一个会议的开始时间早于另一个会议的结束时间并且反之亦然。 # 注意一个会议在另一会议结束时立刻开始不算冲突所以用 。 return start1 end2 and start2 end19. 总结与后续学习方向力扣第836题“矩形重叠”是一道经典的“思维转换”题。它教会我们的远不止如何比较几个坐标。其核心价值在于降维思想和对问题本质的抽象。通过将二维重叠问题分解为两个一维区间问题我们得到了一个时间复杂度O(1)、空间复杂度O(1)的优雅解法代码仅需一行。本文的核心收获不要被“简单”标签迷惑深入理解题目定义正面积重叠边接触不算。掌握投影判断法这是解决轴对齐矩形重叠最高效、最不易出错的方法。警惕边界条件严格使用和来排除边接触情况。代码的优雅在于本质的洞察最简洁的return rec1[0] rec2[2] and rec2[0] rec1[2] and rec1[1] rec2[3] and rec2[1] rec1[3]是建立在对问题深刻理解之上的。后续可以如何深入挑战升级尝试解决LeetCode 223题“矩形面积”它需要你在判断重叠的基础上计算两个矩形覆盖的总面积。维度升级思考如何判断三维空间中的轴对齐长方体是否重叠原理完全一致只需增加Z轴的判断。算法扩展如果矩形不是轴对齐的即旋转矩形如何判断重叠这需要更复杂的几何知识如分离轴定理Separating Axis Theorem, SAT这是游戏物理引擎中常用的算法。实战应用在你的下一个个人项目中如果需要用到碰撞检测或时间调度尝试自己实现这个重叠判断函数体会从算法题到实际应用的转换。刷题的目的不仅是写出能通过测试的代码更是训练一种化繁为简、直击要害的思维能力。矩形重叠这道题就是一个完美的起点。建议你将文中的“一行解法”和其背后的投影思想牢记于心它将成为你算法工具箱中一件锋利而趁手的武器。