LeetCode 223. 矩形面积
目录
题目描述
题意分析
平面上有两个「轴对齐」的矩形，每个矩形用左下角与右上角两个点描述：第一个是
(ax1, ay1)与(ax2, ay2)，第二个是(bx1, by1)与(bx2, by2)。轴对齐意味着四条边分别平行于两条坐标轴，不存在旋转，所以每个矩形完全由「x 区间」和「y 区间」两段区间决定。要求返回两个矩形「覆盖」的总面积。注意「覆盖」这个词：被两个矩形同时压住的那块地方，只能算一次面积。所以答案不是两块面积直接相加，必须把公共部分单独识别出来、且只减掉一次——多减一次会把答案压小，不减则会把重叠区域算成两份。
题目保证
ax1 <= ax2、ay1 <= ay2，另一个矩形同理，所以不会出现左右颠倒的输入，边长天然非负；但允许ax1 == ax2，也就是矩形可以退化成一条线段甚至一个点，此时它的面积是 0。约束里还有一个容易被忽略的信号：坐标是带符号的，绝对值可以到 $10^4$。于是单条边长可达 $2 \times 10^4$，单个矩形面积可达 $4 \times 10^8$，两块相加是 $8 \times 10^8$——虽然还没顶破 32 位有符号整数的上限 $2147483647$，但已经是同一个数量级了。任何一步先乘后转类型的写法都在悬崖边上，把乘法放到 64 位上做是零成本的保险。
需要单独想清楚的边界：两个矩形完全不相交（此时公共部分是 0，而不是某个负数）；只共享一条边或一个角（接触但没有面积，公共部分仍是 0）；一个矩形完全包住另一个；两个矩形完全重合；以及退化成线段的矩形。
解法：容斥计算矩形并集面积
核心思路
两个矩形覆盖的总面积遵循容斥：
\[总面积 = 矩形A面积 + 矩形B面积 - 重叠面积\]轴对齐矩形的交集仍是轴对齐矩形。两个方向可独立求交：重叠宽度等于“较小的右边界减较大的左边界”，重叠高度同理。
若某个方向不相交，这个差值会为负，长度必须截断为 0。因此：
\[overlapX = \max(0,\min(ax2,bx2)-\max(ax1,bx1))\] \[overlapY = \max(0,\min(ay2,by2)-\max(ay1,by1))\]重叠面积为
overlapX * overlapY。任一方向没有正长度，乘积就自然为 0，不需要额外枚举相交类型。
解题步骤
- 分别用宽乘高计算两个矩形的面积。
- 求两个矩形在 x 轴投影的交集长度，并与 0 取最大值。
- 同样求 y 轴投影的交集长度。
- 用两块面积之和减去交集面积。
例如矩形
[-3,0,3,4]与[0,-1,9,2]的面积分别为 24、27，重叠宽高为 3、2，答案为24 + 27 - 6 = 45。
代码实现
class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2,
int bx1, int by1, int bx2, int by2) {
long areaA = (long) (ax2 - ax1) * (ay2 - ay1);
long areaB = (long) (bx2 - bx1) * (by2 - by1);
long overlapX = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
long overlapY = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
return (int) (areaA + areaB - overlapX * overlapY);
}
}
func computeArea(ax1 int, ay1 int, ax2 int, ay2 int,
bx1 int, by1 int, bx2 int, by2 int) int {
areaA := (ax2 - ax1) * (ay2 - ay1)
areaB := (bx2 - bx1) * (by2 - by1)
overlapX := overlapLength(ax1, ax2, bx1, bx2)
overlapY := overlapLength(ay1, ay2, by1, by2)
return areaA + areaB - overlapX*overlapY
}
func overlapLength(startA int, endA int, startB int, endB int) int {
left, right := startA, endA
if startB > left {
left = startB
}
if endB < right {
right = endB
}
if right <= left {
return 0
}
return right - left
}
复杂度分析
- 时间复杂度：$O(1)$。只执行固定次数的比较与算术运算。
- 空间复杂度：$O(1)$。仅使用若干标量变量。
关键点总结
- 总面积不是简单相加，重叠区域被计算了两次，必须减去一次。
- 二维矩形求交可拆成 x、y 两次一维区间求交。
- 交集长度必须截断到 0；两个负长度相乘会产生错误的正面积。
- 边或角接触时至少一个交集长度为 0，因此重叠面积为 0。
易错点总结
- 忘记对交集长度取非负值，会在两个方向都分离时算出虚假的正重叠面积。
- 面积边长是坐标差，不是离散点数，不能额外加 1。
- 强制类型转换要发生在乘法之前，否则整型乘法可能已经溢出。
- 完全包含、完全重合和退化矩形都能由统一公式处理，不需要额外分支。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 836. 矩形重叠 | 简单 | 区间相交判定 |
| 850. 矩形面积 II | 困难 | 扫描线求并集 |
| 1401. 圆和矩形是否有重叠 | 中等 | 点到矩形最近距离 |
| 593. 有效的正方形 | 中等 | 点集的几何性质判定 |