【leetcode】【2022/9/16】850. 矩形面积 II

问题描述：

• 我们给出了一个（轴对齐的）二维矩形列表 rectangles。
  • 对于 rectangle[i] = [x1, y1, x2, y2]，其中 (x1，y1) 是矩形 i 左下角的坐标，(xi1, yi1) 是该矩形左下角的坐标， (xi2, yi2) 是该矩形右上角的坐标。
• 计算平面中所有 rectangles 所覆盖的总面积，任何被两个或多个矩形覆盖的区域应只计算一次。
• 返回总面积，因为答案可能太大，返回 10^9 + 7 的模。
• 输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]。
• 输出：6。
• 图例：
  

核心思路：

• 该题是扫描线题目。【扫描线题目其实就是一类区间问题，如官方题解所讲解的那样，扫描线就是一种离散化的技巧，将大范围的连续的坐标转化成离散的坐标】
• 暴力解法其实不难理解。
  • 矩形面积其实就是宽和高，固定宽，进而求每一个不重叠的高。
  • 具体来说，把一个矩形范围视作两个行和两个列（离散化）。
  • 首先，行与行之间的距离就是宽，宽是固定的。
  • 接着，再处理列与列的重叠关系，因为本题数据量较低，暴力法可以直接搜索所有矩形，选出当前宽所囊括的所有矩形，把这些矩形的两个列作为区间存入一个临时数组中，之后把临时数组排序（也就是把区间排序），最后就遍历区间找出所有范围即可，也就是找出当前宽下所有的矩形高。【这里处理列就是扫描线问题，扫描线问题可以用前缀数组来处理】
• 优化算法就是用线段树处理扫描线部分。【等整理了线段树再重写一下该题】
• 该题难度不算特别大，考察的东西都比较直接，是扫描线的模板题。

代码实现：

• 暴力解法代码实现如下：【逻辑来自下面参考内容中的链接】

  class Solution
  {
  public:
      int rectangleArea(vector<vector<int>>& rectangles)
      {
          int MOD = 1e9+7;
  
          // 行的处理，用于求宽
          vector<int> vec; // 行数组
          for(auto& rect : rectangles) // 把 x1 和 x2 存入数组中
              vec.emplace_back(rect[0]), vec.emplace_back(rect[2]);
          sort(vec.begin(), vec.end());
  
          // 列的处理，用于求高，高的处理就是扫描线的处理
          long long ans = 0;
          for(int i = 1; i < vec.size(); ++i)
          {
              int a = vec[i-1], b = vec[i];
              int len = b - a; // 宽
              if(len == 0) continue;
              vector<vector<int>> tmp;
              for(auto& rect : rectangles) // 列的区间
                  if(rect[0] <= a and b <= rect[2]) tmp.push_back({rect[1], rect[3]});
              sort(tmp.begin(), tmp.end(), [&](const vector<int>& a, const vector<int>& b)
              {
                  return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
              });
              long long cnt = 0, l = -1, r = -1; // 前一个区间
              for(auto& cur : tmp)
              {
                  if(cur[0] > r) // 没有重叠
                  {
                      cnt += r - l;
                      l = cur[0], r = cur[1];
                  }
                  else if(cur[1] > r) // 重叠，更新区间的右边界
                      r = cur[1];
              }
              cnt += r - l;
              ans += cnt * len;
              ans %= MOD;
          }
          return (int)ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45

参考内容：

• 【宫水三叶】扫描线模板题