850. 矩形面积 II--（每日一难phase--day16）

850. 矩形面积 II

我们给出了一个（轴对齐的）二维矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。

计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。

返回 总面积 。因为答案可能太大，返回 109 + 7 的 模 。

示例 1：

输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] 输出：6
解释：如图所示，三个矩形覆盖了总面积为6的区域。 从(1,1)到(2,2)，绿色矩形和红色矩形重叠。
从(1,0)到(2,3)，三个矩形都重叠。

示例 2：

输入：rectangles = [[0,0,1000000000,1000000000]]
输出：49
解释：答案是 1e18 对 (1e9+ 7) 取模的结果， 即 49 。

提示：

1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= xi1, yi1,xi2, yi2 <= 1e9 矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。

解析：

• 将所有矩形横坐标放入set，包括左右两侧;
• 遍历横坐标形成的区间(len=x2-x1)，计算每一个区间的矩形占据的高度(h) ,area = len*h;
• 其中，高度的计算直接遍历所有矩形即可（矩形个数为200，将纵坐标按照从小到大顺序排序），找到左右区间包含（[x1,x2]）的矩形，计算这些矩形高度和。
• 计算矩形高度的时候有三种情况注意判断：
  1，不相交
  2，相交为完全覆盖
  3，相交完全覆盖
  

代码：

class Solution {
    int mod=1e9+7;
public:
    // 将每个举行的横坐标边界放入map,从左往右遍历，求区间面积
    int rectangleArea(vector<vector<int>>& rectangles) {
        set<int> se;
        int n=rectangles.size();
        // 获取所有横坐标，离散化
        for(auto a : rectangles){
            se.insert(a[0]);
            se.insert(a[2]);    
        }
        // 按照纵坐标从小到大排序
        sort(rectangles.begin(),rectangles.end(),[&](vector<int>& l,vector<int>& r){
            if(l[1]==r[1])
                return l[3]<r[3];
            return l[1]<r[1];
        });
        
        long long area=0;
        for(auto it=se.begin();it!=(--se.end());){
            int x=*it,y=*(++it);
            long long len=0,ff=0;
            if(rectangles[0][0]<=x&&rectangles[0][2]>=y)
                len+=rectangles[0][3]-rectangles[0][1],ff=rectangles[0][3];
            for(int i=1;i<n;i++){
                if(rectangles[i][0]<=x&&rectangles[i][2]>=y){
                    // 如果当前矩形的最高处 小于等于 ff（已经计算的最高处），continue；
                    if(rectangles[i][3]<=ff)
                        continue;
                    // 当前矩形下界 大于 已经计算的最高处，没有重合
                    if(rectangles[i][1]>=ff)
                        len+=rectangles[i][3]-rectangles[i][1];
                    // 有重合，但是未全覆盖（如果上边不continue，这里处理不了全覆盖的情况）
                    else 
                        len+=rectangles[i][3]-ff;
                    // 更新最高处
                    ff=rectangles[i][3];
                }
            }
            area+=(long long)(y-x)*len;
            area%=mod;
        }
        return area;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46