【刷穿 LeetCode】223. 矩形面积 : 运用容斥原理求解

题目描述

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

Tag : 「容斥原理」

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

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

• 第一个矩形由其左下顶点 (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^4104<=ax1,ay1,ax2,ay2,bx1,by1,bx2,by2<=104

容斥原理

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

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

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

求交集矩形面积，可以转换为求两矩形在坐标轴上的重合长度，若两矩形在 XX 轴上的重合长度为 xx，在 YY 轴上的重合长度为 yy，则有重合面积为 C = x * yC=x∗y。同时考虑两矩形在任一坐标轴上没有重合长度，则不存在重合面积，因此需要将重合长度与 00 取 \maxmax。

最终答案为 A + B - CA+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)
• 空间复杂度：O(1)O(1)

最后

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

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

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

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