教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于「算法通关手册」AlgoNote 仓库中的 0223. 矩形面积题解 展开。题目属于「几何、数学」分类、难度中等核心是用容斥原理把「两个矩形覆盖的总面积」拆解为「两矩形面积之和减去重叠部分面积」。读完本文你将掌握如何用一维区间交集的方法在 O(1) 时间内求出二维矩形的重叠区域长宽并能够直接迁移到矩形重叠判定0836、多矩形面积并0850等系列问题上。一、题目描述与坐标约定给定两个矩形的左下角、右上角坐标(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)(ax1, ay1)表示第一个矩形左下角坐标(ax2, ay2)表示第一个矩形右上角坐标(bx1, by1)表示第二个矩形左下角坐标(bx2, by2)表示第二个矩形右上角坐标。要求计算出两个矩形覆盖的总面积。题目约定两个矩形的边均与坐标轴平行axis-aligned因此每个矩形都可以用其在 x 轴与 y 轴上的两条投影线段完整刻画矩形 A 在 x 轴上的投影区间为(ax1, ax2)在 y 轴上的投影区间为(ay1, ay2)矩形 B 在 x 轴上的投影区间为(bx1, bx2)在 y 轴上的投影区间为(by1, by2)。在仓库的题目索引 00_05_solutions_list.md 中本题被标注为「几何、数学」标签、中等难度完整题解位于 docs/solutions/0200-0299/rectangle-area.md。二、解题思路容斥原理分解总面积两个矩形覆盖的总面积满足如下恒等式总面积 第一个矩形面积 第二个矩形面积 - 重叠部分面积这是典型的容斥原理应用先把两个矩形的面积直接相加此时重叠区域被重复计算了一次因此必须再减去一次重叠区域的面积。具体分三步分别计算两个矩形的面积矩形面积 宽 × 高 (右上角 x - 左下角 x) × (右上角 y - 左下角 y)求出相交部分的长、宽重叠矩形的宽 两个矩形在 x 轴投影线段的交集长度重叠矩形的高 两个矩形在 y 轴投影线段的交集长度计算重叠部分面积overlap_width × overlap_height若某个方向没有交集则重叠面积为 0。2.1 核心技巧把二维重叠退化为一维区间交集矩形在 x 轴与 y 轴上的投影都是区间两个轴对齐矩形的重叠区域之所以仍是矩形是因为其 x 区间与 y 区间分别独立取交集。两个区间[l1, r1]与[l2, r2]的交集长度为intersection_length max(0, min(r1, r2) - max(l1, l2))当两个区间确实相交时min(r1, r2) max(l1, l2)差值为正即为交集长度当两个区间无交集相离或仅边界相触时min(r1, r2) max(l1, l2)差值 ≤ 0通过外层max(0, ...)把结果钳制为 0。套用到矩形上overlap_width max(0, min(ax2, bx2) - max(ax1, bx1)) overlap_height max(0, min(ay2, by2) - max(ay1, by1))这个「投影区间交集」的视角同样出现在仓库的另一道姊妹题 0836. 矩形重叠题解 中判断两矩形是否重叠只需检查min(rec1[2], rec2[2]) max(rec1[0], rec2[0])x 方向有交集且min(rec1[3], rec2[3]) max(rec1[1], rec2[1])y 方向有交集同时成立即可。本 223 题正是把该「有无交集」的布尔判定升级为「交集长度是多少」的数值计算。三、完整代码实现仓库题解 docs/solutions/0200-0299/rectangle-area.md 给出的参考实现如下class Solution: def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) - int: area_a (ax2 - ax1) * (ay2 - ay1) area_b (bx2 - bx1) * (by2 - by1) overlap_width max(0, min(ax2, bx2) - max(ax1, bx1)) overlap_height max(0, min(ay2, by2) - max(ay1, by1)) area_overlap overlap_width * overlap_height return area_a area_b - area_overlap3.1 逐行解读代码行作用说明area_a (ax2 - ax1) * (ay2 - ay1)计算第一个矩形面积宽 右上角 x − 左下角 x高 右上角 y − 左下角 yarea_b (bx2 - bx1) * (by2 - by1)计算第二个矩形面积同上套用第二个矩形的坐标overlap_width max(0, min(ax2, bx2) - max(ax1, bx1))求重叠宽度x 方向两投影区间的交集长度不相交时为 0overlap_height max(0, min(ay2, by2) - max(ay1, by1))求重叠高度y 方向两投影区间的交集长度不相交时为 0area_overlap overlap_width * overlap_height计算重叠面积宽或高任一为 0 时乘积为 0return area_a area_b - area_overlap容斥求和总面积 面积 A 面积 B − 重叠面积3.2 边界情况验证两矩形完全不相交min(ax2, bx2) max(ax1, bx1)或min(ay2, by2) max(ay1, by1)此时overlap_width或overlap_height被钳制为 0area_overlap 0返回area_a area_b符合预期一个矩形完全包含另一个交集区间长度恰等于较小矩形的宽和高重叠面积等于较小矩形面积总面积等于较大矩形面积仅边界相触共享一条边或一个顶点相触方向交集长度为 0重叠面积为 0总面积仍为两矩形面积之和符合题目对「覆盖面积」的通常定义面积为零的重叠不计入重复覆盖。3.3 复杂度分析时间复杂度O(1)。仅执行常数次算术运算与min/max比较不随输入规模变化空间复杂度O(1)。只使用若干个局部变量无额外数据结构。四、思路延展从两个矩形到矩形系列问题本题的两条核心思想——「投影区间交集」与「容斥去重」——在仓库中可以延伸到更复杂的矩形几何系列题重叠判定0836简单0836. 矩形重叠题解 把 223 题的overlap_width * overlap_height计算退化为布尔判断仅需验证两个方向投影区间是否均有正交集多矩形面积并0850困难0850. 矩形面积 II 题解 将两个矩形的容斥公式推广到任意多个矩形由于重叠区域只能计算一次需要借助「扫描线 动态开点线段树」对 y 方向区间进行覆盖计数再按 x 方向逐段累加面积返回对10^9 7取模的结果完美矩形0391困难0391. 完美矩形题解 进一步要求判断一组小矩形能否无重叠、无缝隙地拼成一个大矩形本质上是面积等式与顶点计数的组合验证。从这两个矩形的简单容斥到扫描线线段树求解面积并再到完美矩形的顶点计数可以看到「区间 容斥 扫描」构成了矩形几何问题的一条清晰进阶路径。读者在掌握本题 O(1) 解法后可按上述顺序在 docs/solutions 目录下继续深入对应题解。五、总结LeetCode 223「矩形面积」是一道典型的「几何 数学」中等题解题公式为总面积 S(A) S(B) − S(重叠)本质是容斥原理重叠区域的宽与高可分别通过两个坐标轴方向上的一维区间交集长度求得max(0, min(r1, r2) - max(l1, l2))是唯一需要掌握的子技巧该技巧同时覆盖了「无重叠」「包含」「相触」等全部边界情况无需任何特判算法时间复杂度 O(1)、空间复杂度 O(1)属于面试中高频出现的「数学公式推导 边界处理」类题目。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解223. Rectangle Area 矩形面积计算LeetCode Go 题解223. Rectangle Area 矩形面积计算 导读 本文讲解 LeetCode 第 223 题「Rectangle Are示例工程开发者指南基于Qwen2.5 Omni架构的ACE-Step Transcriber模型配置与调用方法开发者指南基于Qwen2.5 Omni架构的ACE Step Transcriber模型配置与调用方法 ACE Step Transcriber是一款基于QwLogicStack-LeetCode最大三角形面积LogicStack LeetCode最大三角形面积 题目描述 这是 LeetCode 上的 812. 最大三角形面积 https://link.gitcod教程文档上一篇Play Integrity Fix 终极指南如何让Root设备重新获得Google认证下一篇2025容器存储新范式WinFsp容器存储接口(CSI)实现指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考