力扣836题矩形重叠：从几何原理到Python实现的算法精解

这次我们来看一个经典的算法问题力扣LeetCode第836题——矩形重叠。这个问题本身不涉及复杂的AI模型部署但它是一个考察数学思维和编程基本功的绝佳案例。对于准备技术面试、刷题提升算法能力或者想深入理解几何问题边界判断的开发者来说掌握这道题的解法至关重要。本文的核心不是介绍一个需要安装部署的工具而是深入拆解一个算法问题。我们将从问题本质出发先讲清楚如何判断两个矩形是否重叠然后提供多种Python解决方案并分析其背后的数学原理。无论你是算法新手还是想寻找更优解法的进阶者都能从中获得清晰的解题思路和可直接运行的代码。1. 核心能力速览能力项说明问题类型几何计算、边界判断算法题来源平台力扣 (LeetCode) 第836题核心考察点坐标系统理解、条件判断逻辑、逆向思维输入输出输入为两个矩形的左下角和右上角坐标输出为布尔值True/False时间复杂度O(1)只进行常数次比较运算空间复杂度O(1)只使用固定数量的变量适合场景面试准备、算法学习、几何碰撞检测基础、游戏开发逻辑2. 适用场景与使用边界这道题虽然题目描述简单但其背后蕴含的“分离轴”思想是计算机图形学、游戏物理引擎碰撞检测、UI界面布局计算等领域的基础。理解它你就能处理更复杂的形状重叠问题。它适合谁算法初学者学习如何将几何问题转化为代码逻辑。面试准备者这是一道高频的面试算法题考察逻辑严密性。游戏或图形开发者作为学习2D碰撞检测的入门案例。任何希望提升编程思维的开发者。它能解决什么问题判断两个轴对齐的矩形在二维平面上是否有交集。为更复杂的多边形重叠检测提供基础思路。它的局限性本题限定矩形边与坐标轴平行轴对齐矩形。对于旋转矩形判断逻辑会复杂得多。只判断是否重叠不计算重叠面积或重叠区域。合规性提醒算法解题是完全合规的技术学习活动。本文提供的代码可用于学习、面试准备及合法的项目开发。3. 环境准备与前置条件解决这道题不需要复杂的服务部署或GPU环境只需要一个能运行Python的编程环境。基础环境清单操作系统Windows, macOS, Linux 均可。Python 环境Python 3.6 或以上版本。推荐使用 Anaconda 或直接安装官方Python。代码编辑器或IDEVS Code, PyCharm, Jupyter Notebook甚至系统自带的文本编辑器都可以。力扣账户可选用于在线提交代码、运行测试用例。环境验证打开终端命令行输入以下命令确认Python已正确安装。python --version # 或 python3 --version应显示类似Python 3.8.10的版本信息。4. 问题理解与数学建模在写代码之前必须彻底理解问题。力扣第836题的描述通常是给定两个矩形rec1和rec2它们的表示形式都是包含四个整数的列表[x1, y1, x2, y2]。其中(x1, y1)是矩形左下角的坐标(x2, y2)是矩形右上角的坐标。要求判断这两个矩形是否重叠。关键点解析坐标轴假设平面直角坐标系x轴向右y轴向上。矩形表示[x1, y1, x2, y2]确保了x1 x2且y1 y2。重叠定义两个矩形有公共的正面积区域。仅边或角接触不算重叠根据力扣官方定义。数学建模——逆向思维直接判断“如何重叠”比较繁琐。更高效的方法是判断“如何不重叠”。两个矩形不重叠只可能发生在四种情况一个矩形在另一个的上、下、左、右四个方向。rec1 在 rec2 的左边rec1[2] rec2[0](rec1的右边界 rec2的左边界)rec1 在 rec2 的右边rec1[0] rec2[2](rec1的左边界 rec2的右边界)rec1 在 rec2 的下边rec1[3] rec2[1](rec1的上边界 rec2的下边界)rec1 在 rec2 的上边rec1[1] rec2[3](rec1的下边界 rec2的上边界)如果以上四种情况都不满足那么两个矩形必然重叠。5. 解决方案与代码实现我们将实现两种最主流的解法并提供一个用于测试的框架。5.1 解法一检查不重叠情况投影法这是最直观、最符合人类思维的方法即上述数学建模的直接实现。def isRectangleOverlap(rec1, rec2): 判断两个矩形是否重叠。 :type rec1: List[int] :type rec2: List[int] :rtype: bool # 检查不重叠的四种情况 # rec1 在 rec2 左边 if rec1[2] rec2[0]: return False # rec1 在 rec2 右边 if rec1[0] rec2[2]: return False # rec1 在 rec2 下边 if rec1[3] rec2[1]: return False # rec1 在 rec2 上边 if rec1[1] rec2[3]: return False # 以上情况都不满足则重叠 return True代码解读函数依次检查四种不重叠的条件。只要满足任意一种立即返回False不重叠。全部检查通过则返回True重叠。时间复杂度 O(1)空间复杂度 O(1)。5.2 解法二检查重叠区域区间交集法另一种思路是两个矩形在x轴和y轴上的投影区间必须同时有交集它们才会重叠。计算x轴上的重叠矩形在x轴上的投影是[x1, x2]。两个区间[rec1[0], rec1[2]]和[rec2[0], rec2[2]]有交集的条件是max(rec1[0], rec2[0]) min(rec1[2], rec2[2])。同理y轴上的重叠条件是max(rec1[1], rec2[1]) min(rec1[3], rec2[3])。两个条件必须同时满足。def isRectangleOverlap(rec1, rec2): 判断两个矩形是否重叠区间交集法。 :type rec1: List[int] :type rec2: List[int] :rtype: bool # 检查x轴投影是否有交集 overlap_x max(rec1[0], rec2[0]) min(rec1[2], rec2[2]) # 检查y轴投影是否有交集 overlap_y max(rec1[1], rec2[1]) min(rec1[3], rec2[3]) # x轴和y轴同时有交集则矩形重叠 return overlap_x and overlap_y代码解读overlap_x为True表示在水平方向有重叠部分。overlap_y为True表示在垂直方向有重叠部分。逻辑运算符and确保两个方向都重叠。这种方法代码更简洁是更受推荐的写法。5.3 功能测试与效果验证为了验证代码的正确性我们需要设计测试用例。一个好的测试应覆盖边界情况。测试用例设计明显重叠rec1 [0,0,2,2], rec2 [1,1,3,3]- 应返回True。不重叠左右rec1 [0,0,1,1], rec2 [2,0,3,1]- 应返回False。不重叠上下rec1 [0,0,1,1], rec2 [0,2,1,3]- 应返回False。边接触不算重叠rec1 [0,0,1,1], rec2 [1,0,2,1]- 应返回False。角接触不算重叠rec1 [0,0,1,1], rec2 [1,1,2,2]- 应返回False。完全包含rec1 [0,0,3,3], rec2 [1,1,2,2]- 应返回True。本地测试脚本你可以创建一个Python文件如test_836.py来运行测试。def test_isRectangleOverlap(func): 测试函数传入要测试的解法函数 test_cases [ (([0,0,2,2], [1,1,3,3]), True, Case 1: 明显重叠), (([0,0,1,1], [2,0,3,1]), False, Case 2: 左右不重叠), (([0,0,1,1], [0,2,1,3]), False, Case 3: 上下不重叠), (([0,0,1,1], [1,0,2,1]), False, Case 4: 右边接触), (([0,0,1,1], [1,1,2,2]), False, Case 5: 右上角接触), (([0,0,3,3], [1,1,2,2]), True, Case 6: 完全包含), (([7,8,13,15], [10,8,12,20]), True, Case 7: 复杂重叠), ] print(fTesting function: {func.__name__}) all_passed True for (rec1, rec2), expected, msg in test_cases: result func(rec1, rec2) if result expected: print(f ✓ PASS: {msg}) else: print(f ✗ FAIL: {msg}. Got {result}, expected {expected}. rec1{rec1}, rec2{rec2}) all_passed False print(All tests passed! if all_passed else Some tests failed!) return all_passed # 导入你写的函数或者直接在这里定义 # from solution import isRectangleOverlap # 测试解法一 print( Testing Solution 1 (Check Non-Overlap) ) test_isRectangleOverlap(isRectangleOverlap) # 假设解法一函数叫 isRectangleOverlap # 如果你写了第二种解法比如叫 isRectangleOverlap2 # print(\n Testing Solution 2 (Interval Overlap) ) # test_isRectangleOverlap(isRectangleOverlap2)运行与验证在终端中执行python test_836.py。如果所有测试用例都通过你会看到一串✓ PASS的输出最后显示All tests passed!。这是判断你的解法是否正确的直接标准。6. 算法分析与性能观察虽然这道题的时间复杂度是 O(1)但理解其性能表现和资源占用仍有意义。时间复杂度 O(1)无论矩形坐标值多大算法都只执行固定次数的比较和算术运算通常不超过10次。这意味着它的执行时间恒定且极短。空间复杂度 O(1)算法只使用了几个临时变量如max,min的结果没有使用随输入规模增长的额外数据结构。“性能测试”实践在算法题中性能主要指时间。你可以在力扣提交后查看运行时间分布。对于本題两种解法的运行时间通常都在20-30毫秒左右属于最快的一档。本地测试由于没有力扣的评测环境时间可以忽略不计。如何观察在本地你可以用time模块进行粗略测量但意义不大。更重要的“性能”体现在代码的可读性和健壮性上。区间交集法解法二通常被认为更优雅更不易出错。7. 常见问题与排查方法在实现和调试过程中你可能会遇到以下问题问题现象可能原因排查方式解决方案所有测试用例都失败函数逻辑完全写反检查返回值。不重叠时是否返回了True重新审视四种不重叠条件或区间交集逻辑。边接触的用例返回了True条件判断用了或而不是或仔细检查不等式。重叠需要严格小于。将改为将改为。例如max(x1, x3) min(x2, x4)。“完全包含”用例失败忽略了包含也是重叠的一种理解“重叠”的定义包含一个矩形完全在另一个内部的情况。确保你的逻辑能处理包含关系。区间交集法天然支持。代码在力扣上报错变量名拼写错误或索引越界检查rec1[0]是否写成了rec1(0)或rec1[4]。Python列表索引从0开始有效索引是0,1,2,3。输出结果时对时错输入坐标顺序理解错误确认[x1, y1, x2, y2]是[左下x, 左下y, 右上x, 右上y]。画图辅助理解。假设rec1 [A, B, C, D]则左下角是(A,B)右上角是(C,D)。8. 最佳实践与使用建议优先掌握区间交集法这是更通用、更简洁的解法其思想可以扩展到判断线段、立方体是否重叠等问题。画图辅助遇到几何问题在纸上画出示意图是最高效的调试方法。标出坐标直观地判断重叠与否。编写单元测试像我们上面做的那样针对边界情况边接触、角接触、包含、分离设计测试用例能极大提高代码正确率。理解问题本质不要死记硬背代码。理解“判断不重叠比判断重叠更容易”和“二维重叠需要两个一维区间同时重叠”这两个核心思想。在力扣上练习完成本地测试后务必去力扣官网提交代码。平台会提供更全面的隐藏测试用例并给出运行时间和内存消耗排名。9. 总结与下一步力扣836题“矩形重叠”是一个经典的几何判断问题。它的价值不在于算法有多复杂而在于训练我们将空间问题转化为逻辑条件的能力。掌握区间交集法你就能用几行清晰的代码解决它。最值得尝试的点是自己推导一遍“不重叠”的四种情况然后写出代码再用我们提供的测试用例验证。最容易踩的坑就是边界条件的判断还是。下一步你可以挑战自己尝试计算两个矩形的重叠面积。这需要你在判断重叠的基础上计算出重叠区域的宽度和高度。扩展应用了解游戏开发中的碰撞检测算法如AABB轴对齐包围盒其核心就是本题的扩展。刷题关联在力扣上搜索与“区间”相关的问题如第56题合并区间、第57题插入区间、第252题会议室它们都共享类似的一维区间处理思想。把这个简单的矩形问题吃透你的算法工具箱里就又多了一件应对几何和边界判断问题的利器。建议收藏本文的测试用例和两种解法代码在面试前快速回顾。