🌕🌕 391. 完美矩形

难度: 🌕🌕

问题描述

---

解法

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        // 思路：
        // 找规律
        // 满足以下 2 个条件：
        // 1. 最终矩形面积 == 所有小矩形面积之和
        // 2. 无重复区域 - 记录每个小矩形顶点次数，只有最终矩形的四个顶点只出现了 1 次，其余顶点必两两重合，不可能为奇数次
        int sumArea = 0; // 统计所有小矩形面积
        int minX = rectangles[0][0]; 
        int minY = rectangles[0][1];
        int maxX = rectangles[0][2];
        int maxY = rectangles[0][3];
        HashMap<String, Integer> map = new HashMap<>();

        // 遍历
        for(int[] cur: rectangles) {
            int x = cur[0];
            int y = cur[1];
            int a = cur[2];
            int b = cur[3];
            sumArea += (a - x) * (b - y);
            // 更新最终矩形边界
            if(x <= minX && y <= minY) {
                minX = x;
                minY = y;
            }
            if(a >= maxX && b >= maxY) {
                maxX = a;
                maxY = b;
            }
            // 添加小矩形四个顶点到 map
            String lb = getStr(x, y);
            if(!map.containsKey(lb)) {
                map.put(lb, 1);
            } else {
                map.remove(lb);
            }
            String lt = getStr(x, b);
            if(!map.containsKey(lt)) {
                map.put(lt, 1);
            } else {
                map.remove(lt);
            }
            String rb = getStr(a, y);
            if(!map.containsKey(rb)) {
                map.put(rb, 1);
            } else {
                map.remove(rb);
            }
            String rt = getStr(a, b);
            if(!map.containsKey(rt)) {
                map.put(rt, 1);
            } else {
                map.remove(rt);
            }
        }
        int expArea = (maxX - minX) * (maxY - minY);
        if(sumArea != expArea) {
            return false;
        }
        // 面积总和相等
        return map.containsKey(getStr(minX, minY)) 
        && map.containsKey(getStr(minX, maxY)) 
        && map.containsKey(getStr(maxX, minY))
        && map.containsKey(getStr(maxX, maxY)) 
        && map.size() == 4; // 有且只有四个顶点
    }

    private String getStr(int x, int y) {
        return "" + x + "#" + y;
    }
}

---

输出