题目描述

我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。 每个矩形用左下角的点和右上角的点的坐标来表示。例如， 一个单位正方形可以表示为 [1,1,2,2]。 ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。 完美矩形问题 - 图1 示例：

  1. rectangles = [
  2.   [1,1,3,3],
  3.   [3,1,4,2],
  4.   [1,3,2,4],
  5.   [2,2,4,4]
  6. ]

返回 false。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

解法1：扫描线+差分树状数组

分析：

  • 只考虑矩形的竖线，扫描线从左到右扫描。
  • 每扫描一次，就使用区间查询和区间修改来判断是否有重叠或空缺。
  • 将矩形的所有竖线按照x坐标分组
  • 竖线可以分为两类：入边和出边。在排序时注意将出边排列在入边之前
  • 将y轴出现的坐标离散化

竖线的定义：

  1. // 矩形的一条竖边
  2. struct Line {
  3.     int x, y1, y2;
  4.     bool left;            // 左边还是右边
  5.     Line() {}
  6.     Line(int x, int y1, int y2, bool left) : x(x), y1(y1), y2(y2), left(left) {}
  7.     bool operator<(const Line& b) {
  8.         if (x == b.x) {        // 在x相同时，出边优先
  9.             return left < b.left;
  10.         }
  11.         else {
  12.             return x < b.x;
  13.         }
  14.     }
  15. };

其余代码如下：

  1. // 差分树状数组的定义
  2. struct Diff {
  3.     ...
  4. };
  5. bool isRectangleCover(vector<vector<int>>& rectangles) {
  6.     int rectNum = rectangles.size();
  7.     // 排序所有边，并统计y轴信息
  8.     vector<Line> lines(rectNum << 1);
  9.     map<int, int> yAxis;
  10.     for (int i = 0; i < rectNum; ++i) {
  11.         lines[i << 1] = Line(rectangles[i][0], rectangles[i][1], rectangles[i][3], true);
  12.         lines[(i << 1) + 1] = Line(rectangles[i][2], rectangles[i][1], rectangles[i][3], false);
  13.         yAxis.insert({ rectangles[i][1], 0 });
  14.         yAxis.insert({ rectangles[i][3], 0 });
  15.     }
  16.     sort(lines.begin(), lines.end());
  17.     // 将y轴坐标离散化
  18.     int yMax = yAxis.size() - 1;
  19.     auto yIter = yAxis.begin();
  20.     for (int i = 0; i <= yMax; ++i) {
  21.         yIter->second = i;
  22.         ++yIter;
  23.     }
  24.     // 对边进行分组，同时确定y坐标对应的序号
  25.     vector<pair<int, int>> groups;        // [l, r)下标分组
  26.     int preX = lines[0].x;
  27.     int preI = 0;
  28.     for (int i = 0; i < rectNum << 1; ++i) {
  29.         if (preX != lines[i].x) {
  30.             groups.push_back({ preI, i });
  31.             preX = lines[i].x;
  32.             preI = i;
  33.         }
  34.         lines[i].y1 = yAxis.find(lines[i].y1)->second;
  35.         lines[i].y2 = yAxis.find(lines[i].y2)->second;
  36.     }
  37.     groups.push_back({ preI, lines.size() });
  38.     // 对于按照x坐标划分的每一组竖线：进行区间加法，并判断是否满
  39.     Diff diff(yMax + 1);
  40.     for (int i = 0; i < groups.size() - 1; ++i) {
  41.         for (int j = groups[i].first; j < groups[i].second; ++j) {
  42.             if (lines[j].left) {
  43.                 // 判断是否有重叠
  44.                 if (diff.IntervalSum(lines[j].y1, lines[j].y2) != 0)
  45.                     return false;
  46.                 diff.UpdateInterval(lines[j].y1, lines[j].y2, 1);
  47.             }
  48.             else {
  49.                 diff.UpdateInterval(lines[j].y1, lines[j].y2, -1);
  50.             }
  51.         }
  52.         if (diff.IntervalSum(0, yMax) != yMax)
  53.             return false;
  54.     }
  55.     return true;
  56. }

解法2：点重合+面积法

分析：

  • 完美矩形中的任何顶点，都出现了偶数次；处理最边缘的四个点
  • 光靠点无法排除一些重叠的情况，使用面积判断即可。

代码如下：

bool isRectangleCover(vector<vector<int>>& rectangles) {
    set<pair<int, int>> points;
    int area = 0;
    for (const auto& rect : rectangles) {
        // 面积累计
        area += (rect[3] - rect[1]) * (rect[2] - rect[0]);
        // [0, 1]
        if (points.find({ rect[0], rect[1] }) == points.end())
            points.insert({ rect[0], rect[1] });
        else
            points.erase({ rect[0], rect[1] });
        // [0, 3]
        if (points.find({ rect[0], rect[3] }) == points.end())
            points.insert({ rect[0], rect[3] });
        else
            points.erase({ rect[0], rect[3] });
        // [2, 1]
        if (points.find({ rect[2], rect[1] }) == points.end())
            points.insert({ rect[2], rect[1] });
        else
            points.erase({ rect[2], rect[1] });
        // [2, 3]
        if (points.find({ rect[2], rect[3] }) == points.end())
            points.insert({ rect[2], rect[3] });
        else
            points.erase({ rect[2], rect[3] });
    }
    if (points.size() != 4)
        return false;
    // 确定边际
    int minX = INT32_MAX;
    int minY = INT32_MAX;
    int maxX = INT32_MIN;
    int maxY = INT32_MIN;
    for (const auto& point : points) {
        minX = min(minX, point.first);
        minY = min(minY, point.second);
        maxX = max(maxX, point.first);
        maxY = max(maxY, point.second);
    }
    // 核准面积
    if (area != (maxY - minY) * (maxX - minX))
        return false;
    else
        return true;
}