LeetCode 223. 矩形面积

约 4 分钟
文章信息 11 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节 微软 美团 快手 滴滴 虾皮
标签
数学 几何

题目描述

✅ 223. 矩形面积

image-20260928215256630

image-20260928215256631

image-20260928215256632

题意分析

两个矩形的边都平行于坐标轴，分别由左下角和右上角确定。要求被至少一个矩形覆盖的总面积；重叠部分只能计入一次，边或角的接触不贡献面积。

解法：容斥计算矩形并集面积

核心思路

[!blue]

每个矩形的宽、高分别是右上角坐标减去左下角坐标，二者相乘就是自身面积。先把两个面积相加：只属于其中一个矩形的区域恰好计入一次，同时属于两个矩形的区域计入了两次，所以再减掉一次交集面积，便得到覆盖总面积。

交集中的横坐标必须同时落在两个矩形的横向范围内，因此它的左边界取两个左端点的较大值，右边界取两个右端点的较小值。于是重叠宽度为 max(0, min(ax2, bx2) - max(ax1, bx1))；纵向同理，重叠高度为 max(0, min(ay2, by2) - max(ay1, by1))。

由于矩形与坐标轴平行，横、纵范围相互独立，两段交集组合成的仍是矩形，宽乘高就是交集面积。任一方向没有正长度交集，重叠面积便为 0；完全包含、完全重合及宽或高为 0 的退化矩形也由同一公式处理。

解题步骤

  1. 分别用宽乘高计算两个矩形的面积。
  2. 求 x 轴投影交集的左右边界，用右边界减左边界，再与 0 取最大值得到 overlapX。
  3. 同样计算 y 轴投影的交集长度 overlapY。Go 代码用 overlapLength 复用这两次一维区间求交。
  4. 返回 areaA + areaB - overlapX * overlapY。两个交集长度必须分别截断为非负数，不能先相乘再截断，否则两个负长度会产生虚假的正面积。

代码实现

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)$。仅使用若干标量变量。

关键点总结

[!green]

  • 总面积不是简单相加，重叠区域被计算了两次，必须减去一次。
  • 二维矩形求交可拆成 x、y 两次一维区间求交。
  • 交集长度必须截断到 0；两个负长度相乘会产生错误的正面积。
  • 边或角接触时至少一个交集长度为 0，因此重叠面积为 0。

易错点总结

[!yellow]

  • 忘记对交集长度取非负值，会在两个方向都分离时算出虚假的正重叠面积。
  • 面积边长是坐标差，不是离散点数，不能额外加 1。
  • 重叠面积只减一次；两块面积相加时它被计入两次，减去后正好保留一份。
  • 完全包含、完全重合和退化矩形都能由统一公式处理，不需要额外分支。

相似题目

题目 难度 关联与区别
836. 矩形重叠 简单 矩形是否重叠的边界判断是计算交集面积的基础，本题再用面积和减交集。
850. 矩形面积 II 困难 矩形并面积系列。I 用两个矩形面积减去交集，II 推广到多个矩形，需要扫描线维护覆盖长度。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/49321725
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！