leetcode：223. 矩形面积

题目

给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 顶点和 右上 顶点坐标表示：

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

示例 1：
[中等] 223. 矩形面积 - 图1

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

示例 2：

  1. 输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
  2. 输出：16

解答 & 代码

矩形 1 面积 + 矩形 2 面积 - 重叠面积 

  1. class Solution {
  2. public:
  3.     int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
  4.         int area1 = (ax2 - ax1) * (ay2 - ay1);    // 矩形 1 面积
  5.         int area2 = (bx2 - bx1) * (by2 - by1);    // 矩形 2 面积
  6.         // 如果两个矩形无重叠，则直接返回两个矩形面积之和
  7.         if(ay1 >= by2 || by1 >= ay2 || bx1 >= ax2 || ax1 >= bx2)
  8.             return area1 + area2;
  9.         // 否则返回两个矩形面积之和 - 重叠面积
  10.         else
  11.         {
  12.             int cx1 = max(ax1, bx1);    // 重叠矩形的左下顶点
  13.             int cy1 = max(ay1, by1);
  14.             int cx2 = min(ax2, bx2);    // 重叠矩形的右上顶点
  15.             int cy2 = min(ay2, by2);
  16.             // 重叠矩形面积
  17.             int overLapArea = (cx2 - cx1) * (cy2 - cy1);
  18.             return area1 + area2 - overLapArea;
  19.         }
  20.     }
  21. };

复杂度分析：

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：5.9 MB, 在所有 C++ 提交中击败了 8.46% 的用户

换种写法：

  1. class Solution {
  2. public:
  3.     int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
  4.         int area1 = (ax2 - ax1) * (ay2 - ay1);    // 矩形 1 面积
  5.         int area2 = (bx2 - bx1) * (by2 - by1);    // 矩形 2 面积
  7.         int cx1 = max(ax1, bx1);                // 重叠矩形的左下顶点
  8.         int cy1 = max(ay1, by1);
  9.         int cx2 = min(ax2, bx2);                // 重叠矩形的右上顶点
  10.         int cy2 = min(ay2, by2);
  11.         int width = max(cx2 - cx1, 0);            // 重叠矩形的宽度（若无重叠则取 0）
  12.         int height = max(cy2 - cy1, 0);         // 重叠矩形的高度（若无重叠则取 0）
  13.         int overLapArea = width * height;        // 重叠矩形的面积
  14.         return area1 + area2 - overLapArea;
  15.     }
  16. };

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 89.430% 的用户
  4. 内存消耗：5.8 MB, 在所有 C++ 提交中击败了 84.93% 的用户