391. 完美矩形

给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

哈希表

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles == null || rectangles.length == 0) {
            return true;
        }
        long area = 0;
        int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
        Map cnt = new HashMap<>();
        for (int[] rect : rectangles) {
            int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];
            area += (long) (x2 - x1) * (y2 - y1);

            minX = Math.min(minX, x1);
            minY = Math.min(minY, y1);
            maxX = Math.max(maxX, x2);
            maxY = Math.max(maxY, y2);

            Point point1 = new Point(x1, y1);
            Point point2 = new Point(x1, y2);
            Point point3 = new Point(x2, y1);
            Point point4 = new Point(x2, y2);

            cnt.put(point1, cnt.getOrDefault(point1, 0) + 1);
            cnt.put(point2, cnt.getOrDefault(point2, 0) + 1);
            cnt.put(point3, cnt.getOrDefault(point3, 0) + 1);
            cnt.put(point4, cnt.getOrDefault(point4, 0) + 1);
        }

        Point pointMinMin = new Point(minX, minY);
        Point pointMinMax = new Point(minX, maxY);
        Point pointMaxMin = new Point(maxX, minY);
        Point pointMaxMax = new Point(maxX, maxY);
        if (area != (long) (maxX - minX) * (maxY - minY) ||
                cnt.getOrDefault(pointMinMin, 0) != 1 ||
                cnt.getOrDefault(pointMinMax, 0) != 1 ||
                cnt.getOrDefault(pointMaxMin, 0) != 1 ||
                cnt.getOrDefault(pointMaxMax, 0) != 1) {
            return false;
        }

        cnt.remove(pointMinMin);
        cnt.remove(pointMinMax);
        cnt.remove(pointMaxMin);
        cnt.remove(pointMaxMax);

        for (Map.Entry entry : cnt.entrySet()) {
            int value = entry.getValue();
            if (value != 2 && value != 4) {
                return false;
            }
        }
        return true;
    }
}

class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        return x + y;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Point) {
            Point point2 = (Point) obj;
            return this.x == point2.x && this.y == point2.y;
        }
        return false;
    }
}

扫描线

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int len = rectangles.length * 2, ids = 0;
        int[][] re = new int[len][4];
        //初始化re数组,组成[横坐标,纵坐标下顶点,纵坐标上顶点,矩形的左边or右边标志]
        for (int[] i : rectangles) {
            re[ids++] = new int[]{i[0], i[1], i[3], 1};
            re[ids++] = new int[]{i[2], i[1], i[3], -1};
        }
        //排序,按照横坐标进行排序,横坐标相等就按纵坐标排序
        Arrays.sort(re, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
        //操作每一个顶点，判断是否符合要求
        for (int i = 0; i < len; ) {
            //如果该边是矩形的左边界,就加入left
            List left = new ArrayList<>();
            //如果该边是矩形的左边界,就加入right
            List right = new ArrayList<>();
            //标志该边是不是 矩形的左边
            boolean flag = i == 0;
            //判断横坐标相同情况下的边
            int x = i;
            while (x < len && re[x][0] == re[i][0]) x++;
            //判断该横坐标的 边是不是符合要求
            while (i < x) {
                //因为是引用数据类型,所以可以直接操作list,相当于操作left或者right
                List list = re[i][3] == 1 ? left : right;
                if (list.isEmpty()) {
                    list.add(re[i++]);
                } else {
                    int[] pre = list.get(list.size() - 1);
                    int[] cur = re[i++];
                    //有重叠 直接放回false
                    if (cur[1] < pre[2]) return false;
                    if (cur[1] == pre[2]) pre[2] = cur[2];
                    else list.add(cur);
                }
            }
            //判断边是中间边还是边界边
            if (!flag && x < len) {
                //如果是中间边 判断左右是不是相等
                if (left.size() != right.size()) return false;
                for (int j = 0; j < left.size(); ++j) {
                    if (left.get(j)[2] != right.get(j)[2] || left.get(j)[1] != right.get(j)[1]) return false;
                }
            } else {
                //如果是边界边判断是不是一条
                if (left.size() != 1 && right.size() == 0 || left.size() == 0 && right.size() != 1) return false;
            }
        }
        return true;
    }
}