【力扣 leetcode】850：矩形面积II

- 日理万妓 2023-10-09 14:45 47阅读 0赞

## 每日进步 ##

*  **集合：** `Set<Integer> set = new HashSet<Integer>();`
    
     *  无存放顺序，无重复元素。
 *  **列表：** `List<Integer> hbound = new ArrayList<Integer>(set);`
    
     *  有存放顺序，有重复元素。
 *  **排序：** `Collections.sort(list, new PriceComparator());`
    
     *  `list`：待排序列表。
     *  `PriceComparator`：比较器。
 *  **扫描线**
 *  **离散化**

## 题目 ##

我们给出了一个（轴对齐的）二维矩形列表`rectangles`。 对于`rectangle[i] = [x1, y1, x2, y2]`，其中`（x1，y1）`是矩形`i`左下角的坐标，`(xi1, yi1)`是该矩形左下角的坐标，`(xi2, yi2)`是该矩形右上角的坐标。  
计算平面中所有`rectangles`所覆盖的**总面积** 。任何被两个或多个矩形覆盖的区域应只计算一次 。  
返回**总面积**。因为答案可能太大，返回  1 0 9 + 7 10^9+7 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)，三个矩形都重叠。  
        ![在这里插入图片描述][4dce1b0b521041ce9390e632fc004c33.png_pic_center]
 *  **示例2：**
    
     *  **输入：** rectangles = \[\[0,0,1000000000,1000000000\]\]
     *  **输出：** 49
     *  **解释：** 答案是1018对(109 + 7)取模的结果，即49。
 *  **提示：**
    
     *  1 <= rectangles.length <= 200
     *  rectanges\[i\].length = 4
     *  0 <= xi1, yi1, xi2, yi2 <= 109
     *  矩形叠加覆盖后的总面积不会超越  2 63 − 1 2^\{63\}-1 263−1 ，这意味着可以用一个64位有符号整数来保存面积结果。

> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/rectangle-area-ii  
> 著作权归领扣网络所有。本文仅供个人学习，非商用。

## 题解 ##

**扫描线**和**离散化**：  
通过矩形的上下边界对扫描线分段，通过矩形的左右边界对整个扫描过程进行离散化。具体思想可结合代码中注释进行思考。

class Solution {
        
        public int rectangleArea(int[][] rectangles) {
        
            int n = rectangles.length;
            final int MOD = 1000000007;
    
            // 保存所有矩形的上下边界
            Set<Integer> set = new HashSet<Integer>();
            for (int i = 0; i < n; i++){
        
                set.add(rectangles[i][1]);
                set.add(rectangles[i][3]);
            }
            List<Integer> hbound = new ArrayList<Integer>(set);
            Collections.sort(hbound);
    
            // 扫描线分段
            int m = hbound.size();
            int[] seq = new int[m-1];
            // length 的信息通过 hbound[i+1] - hbound[i] 获得
    
            // 保存矩形的左右边界 及相关信息
            List<int[]> sweep = new ArrayList<int[]>();
            for (int i = 0; i < n; i++){
        
                sweep.add(new int[]{
        rectangles[i][0], i, 1});
                sweep.add(new int[]{
        rectangles[i][2], i, -1});
            }
    
            // 按横坐标大小对左右边界排序
            Collections.sort(sweep, (a, b) -> {
        
                if (a[0] != b[0])
                    return a[0] - b[0];
                else if (a[1] != b[1])
                    return a[1] - b[1];
                else
                    return a[2] - b[2];
            });
    
            // 扫描
            long sum = 0;
            for (int i = 0; i < sweep.size()-1; i++){
        
                // 搜索所有横坐标相同的边
                int j = i;
                while(j < sweep.size()-1 && sweep.get(j+1)[0] == sweep.get(i)[0]){
        
                    j++;
                }
    
                if (j == sweep.size()-1)
                    break;
    
                // 所有横坐标相同的边一起处理
                for (int k = i; k <= j; k++){
        
                    int id = sweep.get(k)[1];
                    int diff = sweep.get(k)[2];
                    int dobor = rectangles[id][1];  // 下边界
                    int upbor = rectangles[id][3];  // 上边界
    
                    // 检索每一段是否被覆盖
                    for (int x = 0; x < m-1; x++){
        
                        if (dobor <= hbound.get(x) && upbor >= hbound.get(x+1))
                            seq[x] += diff;
                    }
                }
                
                // 计算覆盖的边界长度
                int cover = 0;  // 覆盖的边界长度
                for (int x = 0; x < m-1; x++){
        
                    if (seq[x] > 0)
                        cover += (hbound.get(x+1) - hbound.get(x));
                }
    
                // 计算面积
                int width = sweep.get(j+1)[0] - sweep.get(j)[0];
                sum += (long)cover * width;
    
                i = j;
            }
    
            return (int)(sum % MOD);
        }
    }

[4dce1b0b521041ce9390e632fc004c33.png_pic_center]: https://img-blog.csdnimg.cn/4dce1b0b521041ce9390e632fc004c33.png#pic_center