LeetCode 223. 矩形面积

简介: LeetCode 223. 矩形面积

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

提示:

  • -104 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 104

题解

分析

简单理解题意就是:给我们4个点,分别是两个矩形的两个对角顶点,我们需要算出两个矩形在平面上覆盖的总面积,两个矩形的排布主要有以下4中情况:

(1)不相交

两个矩形不相交的情况有两种,因为输入的顶点是按顺序输入下顶点和上顶点,所以左右不相交的情况可以这样进行判断:(ax2 < bx1 || bx2 < ax1),上下不相交的情况可以这样进行判断:(by1 > ay2 || ay1 > by2)。这两种情况下两个矩形覆盖的总面积即为两个矩形的面积之和。

(2)相交或包含

如上图,我们给横坐标和纵坐标排了个序,横坐标从左到右分别为x1、x2、x3、x4,纵坐标从上到下分别为y1、y2、y3、y4,不难发现,两个矩形相交的面积坐标为x2、x3、y2、y3。让我们再来看看包含的情况:

不难看出,包含情况下的矩形亦如上文分析那样,我们只需要找出x2、x3、y2、y3就可以算出两个矩形相交部分的面积 ,再用总面积减去这部分的面积即为两个矩形覆盖的总面积。

代码
/**
 * @param {number} ax1
 * @param {number} ay1
 * @param {number} ax2
 * @param {number} ay2
 * @param {number} bx1
 * @param {number} by1
 * @param {number} bx2
 * @param {number} by2
 * @return {number}
 */
var computeArea = function (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
  const area = (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1);
  if (ax2 < bx1 || bx2 < ax1) return area;
  if (by1 > ay2 || ay1 > by2) return area;
  let x = [ax1, ax2, bx1, bx2],
    y = [ay1, ay2, by1, by2];
  x = x.sort((a, b) => {
    return a - b;
  });
  y = y.sort((a, b) => {
    return a - b;
  });
  return area - (x[2] - x[1]) * (y[2] - y[1]);
};
目录
相关文章
|
7月前
|
存储
leetcode2975. 移除栅栏得到的正方形田地的最大面积
leetcode2975. 移除栅栏得到的正方形田地的最大面积
45 1
|
6月前
|
存储 SQL 算法
LeetCode 题目 85:最大矩形
LeetCode 题目 85:最大矩形
|
6月前
|
存储 SQL 算法
LeetCode面试题84:柱状图中最大的矩形
LeetCode面试题84:柱状图中最大的矩形
|
7月前
|
算法
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
49 3
|
7月前
|
算法 定位技术
【leetcode】剑指 Offer II 105. 岛屿的最大面积-【深度优先DFS】
【leetcode】剑指 Offer II 105. 岛屿的最大面积-【深度优先DFS】
77 0
|
7月前
代码随想录Day51 完结篇 LeetCode T84 柱状图的最大矩形
代码随想录Day51 完结篇 LeetCode T84 柱状图的最大矩形
42 0
|
7月前
|
算法 测试技术 C#
【单调栈】【区间合并】LeetCode85:最大矩形
【单调栈】【区间合并】LeetCode85:最大矩形
|
7月前
|
算法 测试技术 C#
【单调栈]LeetCode84: 柱状图中最大的矩形
【单调栈]LeetCode84: 柱状图中最大的矩形
|
7月前
leetcode-695:岛屿的最大面积
leetcode-695:岛屿的最大面积
57 0
|
7月前
leetcode-363:矩形区域不超过 K 的最大数值和
leetcode-363:矩形区域不超过 K 的最大数值和
41 0