leetcode 850. Rectangle Area II | 850. 矩形面积 II（递归分割未重叠矩形）

港控/mmm° 2022-09-07 12:21 153阅读 0赞

## 题目 ##

[https://leetcode.com/problems/rectangle-area-ii/][https_leetcode.com_problems_rectangle-area-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

没有看懂官方答案，评论区有一种解法写的挺通俗的：

[Clean Recursive Solution \[Java\]][Clean Recursive Solution _Java]

The idea here is to maintain a list of non-overlapping rectangles to calculate final area.  
If a new rectangle does not overlap with any of the existing rectanlges, add it to the list.  
If there is an overlap, split the non-overlapping regions of the rectangle into smaller rectangles and compare with the rest of the list.

For example, when a new rectangle (green) is compared with the current rectangle (blue), the non-overlapping regions can be split into two smaller rectangles. Rectangle 1 will be covered by the first overlapping case in addRectangle() and rectangle 2 will be covered by the third case. Rectangle 3 overlaps with the current rectangle and need not be considered.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]  
看了之后自己又实现了一遍：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

class Solution { 
        // 0左 1下 2右 3上
        public static final int L = 0;
        public static final int D = 1;
        public static final int R = 2;
        public static final int U = 3;
    
        public int rectangleArea(int[][] rectangles) { 
            ArrayList<int[]> list = new ArrayList<>();
            for (int[] cur : rectangles) { 
                addRec(cur, list, 0);
            }
    
            long sum = 0;
            for (int[] r : list) { 
                sum += ((long) r[U] - r[D]) * (r[R] - r[L]) % 1000000007;
            }
            return (int) (sum % 1000000007);
        }
    
    
        public void addRec(int[] cur, ArrayList<int[]> list, int index) { 
            // 全部没有重叠
            if (index >= list.size()) { 
                list.add(cur);
                return;
            }
            int[] r = list.get(index);
            // 当前没有重叠: cur右边界小于r左边界|cur左边界大于r右边界|cur下边界大于r上边界|cur上边界小于r下边界
            if (cur[R] <= r[L] || cur[L] >= r[R] || cur[D] >= r[U] || cur[U] <= r[D]) { 
                addRec(cur, list, index + 1);
                return;
            }
            // cur的左边界更左
            if (cur[L] < r[L]) addRec(new int[]{ cur[L], cur[D], r[L], cur[U]}, list, index + 1);
            // cur的右边界更右
            if (cur[R] > r[R]) addRec(new int[]{ r[R], cur[D], cur[R], cur[U]}, list, index + 1);
            // cur的下边界更下
            if (cur[D] < r[D]) addRec(new int[]{ Math.max(cur[L], r[L]), cur[D], Math.min(cur[R], r[R]), r[D]}, list, index + 1);
            // cur的上边界更上
            if (cur[U] > r[U]) addRec(new int[]{ Math.max(cur[L], r[L]), r[U], Math.min(cur[R], r[R]), cur[U]}, list, index + 1);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]

[https_leetcode.com_problems_rectangle-area-ii]: https://leetcode.com/problems/rectangle-area-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/68b1cbf93cda4a6689c1af284cb3ba2e.png
[Clean Recursive Solution _Java]: https://leetcode.com/problems/rectangle-area-ii/discuss/138028/Clean-Recursive-Solution-Java
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/ee4d7ed223774801abe930fd9a14e465.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/0d2cf17ee3184fbe861fba1236068b45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/322d2f3dd49343829a156303fe74400a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 4]: /images/20220829/be062bc035934822a72623166ad3afae.png