题目

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

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

输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] 输出：true 解释：5 个矩形一起可以精确地覆盖一个矩形区域。

示例 2：

输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。
示例 3：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]] 输出：false 解释：图形顶端留有空缺，无法覆盖成一个矩形。

示例 4：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]] 输出：false 解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

提示：

1 <= rectangles.length <= 2 * 104
rectangles[i].length == 4
-105 <= xi, yi, ai, bi <= 105
通过次数10,574提交次数24,441

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

解题思路

今天这道题可以使用扫描线来做，扫描线理解起来比较简单，但是，代码着实难写，所以，我们使用一种更容易理解的方法：找规律！

题目要求：所有矩形一起 精确 覆盖了某个矩形区域，可以得出以下几个结论：

• 不能出现空缺；
• 不能出现重叠；
• 所有小矩形合在一起是大矩形；

通过以上结论，我们可知，所有小矩形的面积之和等于大矩形的面积，所以，我们可以先找出大矩形的左下角和右上角，然后求出所有小矩形的面积之和与大矩形的面积比较，如果不相等，可以直接返回 false。

那么，是否只考虑面积相等就可以了呢？

显然不行，因为有可能正好空缺一块，且重叠一块，这样算出来的总面积也会相等，但不能做到精确覆盖，所以，我们还需要考虑其他条件。

观察下面两图，左边为完美矩形，右边为非完美矩形，在完美矩形中，除了四个顶点之外，其它相交的点出现的次数都是偶数次，而非完美矩形不符合这个条件，所以，我们可以检测出现一次的点的数量，并检测它们是不是正好为四个顶点。

作者：tong-zhu
链接：https://leetcode-cn.com/problems/perfect-rectangle/solution/tong-ge-lai-shua-ti-la-zhao-gui-lu-ji-ba-oszq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解题代码

class Solution {
    public boolean isRectangleCover(int[][] r) {
        //解题思路：完美矩形 只有四个基数坐标次数出现
        //面积相等
        //取最大矩阵的四个坐标（最大值用 整形的最小值比较，反之最大值）
        int left = Integer.MAX_VALUE;
        int bottom = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        int top = Integer.MIN_VALUE;
        int sum = 0; //记录小矩阵的面积
        Set<String> set = new HashSet<>();
        for(int i = 0; i < r.length; i++ ) {
            int[] t = r[i];
            left = Math.min(left,t[0]); 
            bottom = Math.min(bottom,t[1]);
            right = Math.max(right,t[2]);
            top = Math.max(top,t[3]);
            sum += caculateArea(t[0],t[1],t[2],t[3]);
            String[] strings = new String[4];
            strings[0] = merge(t[0],t[1]); //左下
            strings[1] = merge(t[0],t[3]); //左上
            strings[2] = merge(t[2],t[1]); //右下
            strings[3] = merge(t[2],t[3]); //右上
            for(int j = 0; j < strings.length; j++) {
                if(set.contains(strings[j]) ) {
                    set.remove(strings[j]);
                } else {
                    set.add(strings[j]);
                }
            }
        }
        if(set.size() == 4 && set.contains(merge(left,bottom) ) 
                           && set.contains(merge(left,top) )
                           && set.contains(merge(right,bottom) )
                           && set.contains(merge(right,top) ) ) {
            return sum == caculateArea(left,bottom,right,top);
        }
        return false;
    }
    private int caculateArea(int left,int bottom,int right,int top) {
        return (right - left) * (top - bottom);
    }
    private String merge(int a,int b) {
        return "" + a + b;
    }
}