LC 223. 矩形面积

题目描述

这是 LeetCode 上的 223. 矩形面积 ，难度为 中等。

给你 二维 平面上两个 由直线构成的 矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示：

• 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
• 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

示例 1：

输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2

输出：45

示例 2：

输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2

输出：16

提示：

• -$10^4 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4$

---

容斥原理

首先在给定左下顶点和右上顶点的情况下，计算矩形面积为 $(x2 - x1) * (y2 - y1)$。

因此，起始时我们可以先直接算得给定的两个矩形的面积 $A$ 和 $B$，并进行累加。

剩下的，我们需要求得两矩形的交集面积，利用「容斥原理」，减去交集面积，即是答案。

求交集矩形面积，可以转换为求两矩形在坐标轴上的重合长度，若两矩形在 $X$ 轴上的重合长度为 $x$，在 $Y$ 轴上的重合长度为 $y$，则有重合面积为 $C = x * y$。同时考虑两矩形在任一坐标轴上没有重合长度，则不存在重合面积，因此需要将重合长度与 $0$ 取 $\max$。

最终答案为 $A + B - C$ 。

代码；

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int x = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
        int y = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
        return (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - (x * y);
    }
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.223 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。