leetcode

leetcode 223题

Posted by franki on September 20, 2021

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

思路

先求出两个矩形的面积，再计算重叠矩形的面积，相减就是结果

代码

// Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
// {[-3, 0] [3, 4]} {[0, -1], [9, 2]}

function computeArea(A, B, C, D, E, F, G, H) {
  const x0 = Math.max(A, E);
  const y0 = Math.max(B, F);
  const x1 = Math.min(C, G);
  const y1 = Math.min(D, H);
  const area1 = calArea(A, B, C, D);
  const area2 = calArea(E, F, G, H);
  const area3 = calArea(x0, y0, x1, y1);
  return area1 + area2 - area3;
}

function calArea(x0, y0, x1, y1) {
  const l = Math.abs(x1 - x0);
  const h = Math.abs(y1 - y0);

  if (l <= 0 || h <= 0) {
    return 0;
  }

  return l * h;
}

复杂度分析

  • 时间复杂度：O(N)
  • 空间复杂度：O(1)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG
    FRIENDS