LeetCode - 850 矩形面积 II

🕗 发布于 2024-09-27 07:39 leetcode Java JavaScript Python C

题目来源

850. 矩形面积 II - 力扣（LeetCode）

题目描述

给你一个轴对齐的二维数组 rectangles 。

对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形左下角的坐标， (xi2, yi2) 是该矩形右上角的坐标。

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

返回总面积。因为答案可能太大，返回 10^9 + 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
解释：答案是 1018 对 (109 + 7) 取模的结果， 即 49 。

提示

1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= xi1, yi1, xi2, yi2 <= 10^9

题目解析

本题如果从 ”面“ 的角度去思考，比如：所有矩形的面积 - 矩形交集部分的面积 = 最终面积。

两个矩形的交集很容易求解，比如下面图示

虽然矩形交集很容易求解，但是想要求出所有交集，则需要让每个矩形和剩余其他矩形尝试比较，得出交集。同时求出交集矩形后，这些交集矩形也是可能互相重叠的。。。交集的交集矩形也是可能互相重叠的。。。这样是无穷无尽的求解。因此这个思路不可取。

本题如果从 ”线“ 的角度去思考，如下图所示，从假设有一条扫描线 x = c（x1 ≤ c ≤ x4），从左向右扫描，每扫描到一个位置，则判断该位置是否有矩形覆盖，如果有矩形覆盖，比如：

图1 ~ 图3 中扫描线只覆盖到了矩形[左下角(x1,y1),右上角(x2,y2)]，因此矩形覆盖的高度为 ( y2 - y1)，对应扫描线扫描出的矩形面积 = (x3 - x1) * ( y2 - y1)
图4 ~ 图5 中扫描线覆盖了两个矩形，分别是 [左下角(x1,y1),右上角(x2,y2)] 和 [左下角(x3,y3),右上角(x4,y4)]，因此矩形覆盖的高度区间也有两个： [y1, y2] 和 [y3, y4]，而这两个区间又是具有重叠部分的，因此我们可以转化为区间问题，利用区间问题解法，求解出所有区间的不重叠长度之和 height 。具体求解过程在下面。那么扫描线扫描出来的面积为 (x2 - x3) * h。

首先，排序区间，按照起始位置升序，如果起始位置相同，则按照结束位置降序
然后，遍历区间，假设当前区间是 [start, end]，上一个区间是 [last_start, last_end]，

若 last_end >= end，那么说明当前区间被上一个区间完全覆盖，可以继续忽略当前区间（因为当前区间的长度已经在上一个区间被统计过了）
若 last_end < end，那么当前区间的非重叠部分为 [max(start, last_end), end]，统计该部分长度：height += end - max(start, last_end)，并更新last_end = end
最后，我们就求出了区间组所有区间覆盖的不重叠长度了。

上面这种思路就是 ”扫描线算法“，扫描线法可以将 "面" 的问题，分解为 "线" 的问题，将 "矩形（面）交集问题" 降解为 "区间（线）交集问题"。

C源码实现

#define MAX_N 200
#define MOD (1e9 + 7)

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int cmp2(const void* a, const void* b) {
    int* A = (int*)a;
    int* B = (int*)b;

    return A[0] != B[0] ? A[0] - B[0] : B[1] - A[1];
}

int rectangleArea(int** rectangles, int rectanglesSize, int* rectanglesColSize) {
    // 统计所有矩形的左边边、右边边所在位置的x坐标
    int listX[MAX_N];
    int listX_size = 0;

    for (int i = 0; i < rectanglesSize; i++) {
        listX[listX_size++] = rectangles[i][0]; // 矩形左边边x坐标位置
        listX[listX_size++] = rectangles[i][2]; // 矩形右边边x坐标位置
    }

    // 所有x坐标升序（每个x视为一条扫描线）
    qsort(listX, listX_size, sizeof(int), cmp);

    // 记录所有矩形并集面积
    long ans = 0;

    for (int i = 1; i < listX_size; i++) {
        // 前一个扫描线x坐标
        int preX = listX[i - 1];
        // 当前扫描线x坐标
        int curX = listX[i];

        // 相邻两个扫描线的距离
        long width = curX - preX;

        // 距离为0, 则跳过
        if (width == 0)
            continue;

        // 将在[x1,x2]区间上的矩形片段（垂直方向高度区间）收集起来
        int lines[MAX_N][2];
        int lines_size = 0;

        // 遍历每个矩形
        for (int j = 0; j < rectanglesSize; j++) {
            // 矩形左上角坐标(x1,y1), 矩形右下角坐标(x2,y2)
            int x1 = rectangles[j][0], y1 = rectangles[j][1],
                    x2 = rectangles[j][2], y2 = rectangles[j][3];

            // 如果矩形包含了 [x1, x2] 区间
            if (x1 <= preX && curX <= x2) {
                // 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y2, y1]
                lines[lines_size][0] = y1;
                lines[lines_size][1] = y2;
                lines_size++;
            }
        }

        // 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序：按照起始位置升序, 如果起始位置相同, 则按照结束位置降序，这样排序的目的是保证排序后，前面的区间尽可能可以覆盖后面的区间
        qsort(lines, lines_size, sizeof(lines[0]), cmp2);

        // 记录lines多个区间，求长度之和，（重叠部分只计算一次）
        long height = 0;

        int last_end = -1;
        for (int j = 0; j < lines_size; j++) {
            int start = lines[j][0];
            int end = lines[j][1];

            // 如果 last_end >= end, 则当前区间被上一个区间完全覆盖，因此可以跳过
            // 如果 last_end < end
            if (last_end < end) {
                // 则当前区间的不重叠部分是 [max(start, last_end), end]
                height += end - (int)fmax(start, last_end);
                // 更新last_end
                last_end = end;
            }
        }

        // 当前扫描线扫描到的面积为 width * height
        ans += width * height;
        ans %= (int)MOD;
    }

    return (int)ans;
}

C++源码实现

#define MOD (1E9 + 7)

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        // 统计所有矩形的左边边、右边边所在位置的x坐标
        vector<int> listX;
        for (vector<int>& rect : rectangles) {
            listX.emplace_back(rect[0]); // 矩形左边边x坐标位置
            listX.emplace_back(rect[2]); // 矩形右边边x坐标位置
        }

        // 所有x坐标升序（每个x视为一条扫描线）
        sort(listX.begin(), listX.end());

        // 记录所有矩形并集面积
        long ans = 0;

        for (int i = 1; i < listX.size(); i++) {
            // 前一个扫描线x坐标
            int preX = listX[i - 1];
            // 当前扫描线x坐标
            int curX = listX[i];

            // 相邻两个扫描线的距离
            long width = curX - preX;

            // 距离为0, 则跳过
            if (width == 0)
                continue;

            // 将在[x1,x2]区间上的矩形片段（垂直方向高度区间）收集起来
            vector<vector<int>> lines;

            // 遍历每个矩形
            for (vector<int>& rect : rectangles) {
                // 矩形左下角坐标(x1,y1), 矩形右上角坐标(x2,y2)
                int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];

                // 如果矩形包含了 [x1, x2] 区间
                if (x1 <= preX && curX <= x2) {
                    // 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]
                    lines.emplace_back(vector<int>{y1, y2});
                }
            }

            // 将处于水方向区间 [x1, x2]
            // 的所有垂直方向区间排序：按照起始位置升序, 如果起始位置相同,
            // 则按照结束位置降序，这样排序的目的是保证排序后，前面的区间尽可能可以覆盖后面的区间
            sort(lines.begin(), lines.end(),
                 [](vector<int>& lineA, vector<int>& lineB) {
                     if (lineA[0] != lineB[0]) {
                         return lineA[0] < lineB[0];
                     } else {
                         return lineA[1] > lineB[1];
                     }
                 });

            // 记录lines多个区间，求长度之和，（重叠部分只计算一次）
            long height = 0;

            int last_end = INT_MIN;
            for (vector<int>& line : lines) {
                int start = line[0];
                int end = line[1];

                // 如果 last_end >= end,
                // 则当前区间被上一个区间完全覆盖，因此可以跳过 如果 last_end <
                // end
                if (last_end < end) {
                    // 则当前区间的不重叠部分是 [max(start, last_end), end]
                    height += end - max(start, last_end);
                    // 更新last_end
                    last_end = end;
                }
            }

            // 当前扫描线扫描到的面积为 width * height
            ans += width * height;
            ans %= (int) MOD;
        }

        return (int) ans;
    }
};

Java源码实现

class Solution {
    public int rectangleArea(int[][] rectangles) {
        // 统计所有矩形的左边边、右边边所在位置的x坐标
        ArrayList<Integer> listX = new ArrayList<>();
        for (int[] rect : rectangles) {
            listX.add(rect[0]);
            listX.add(rect[2]);
        }

        // 所有x坐标升序（每个x视为一条扫描线）
        listX.sort((a, b) -> a - b);

        // 记录所有矩形并集面积
        long ans = 0;

        for (int i = 1; i < listX.size(); i++) {
            // 前一个扫描线x坐标
            int preX = listX.get(i - 1);
            // 当前扫描线x坐标
            int curX = listX.get(i);

            // 相邻两个扫描线的距离
            int width = curX - preX;

            // 距离为0, 则跳过
            if (width == 0)
                continue;

            // 将在[x1,x2]区间上的矩形片段（垂直方向高度区间）收集起来
            ArrayList<int[]> lines = new ArrayList<>();

            // 遍历每个矩形
            for (int[] rect : rectangles) {
                // 矩形左下角坐标(x1,y1), 矩形右上角坐标(x2,y2)
                int x1 = rect[0], y1 = rect[1], x2 = rect[2], y2 = rect[3];

                // 如果矩形包含了 [x1, x2] 区间
                if (x1 <= preX && curX <= x2) {
                    // 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]
                    lines.add(new int[] { y1, y2 });
                }
            }

            // 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序：按照起始位置升序, 如果起始位置相同,则按照结束位置降序，
            // 这样排序的目的是保证排序后，前面的区间尽可能可以覆盖后面的区间
            lines.sort((lineA, lineB) -> lineA[0] != lineB[0] ? lineA[0] - lineB[0] : lineB[1] - lineA[1]);

            // 记录lines多个区间，求长度之和，（重叠部分只计算一次）
            int height = 0;

            int last_end = -1;
            for (int[] line : lines) {
                int start = line[0];
                int end = line[1];

                // 如果 last_end >= end, 则当前区间被上一个区间完全覆盖，因此可以跳过
                // 如果 last_end < end
                if (last_end < end) {
                    // 则当前区间的不重叠部分是 [max(start, last_end), end]
                    height += end - Math.max(start, last_end);
                    // 更新last_end
                    last_end = end;
                }
            }

            // 当前扫描线扫描到的面积为 width * height
            ans += (long) width * height;
            ans %= (int) (1e9 + 7);
        }

        return (int) ans;
    }
}

Python源码实现

class Solution(object):
    def rectangleArea(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: int
        """
        # 统计所有矩形的左边边、右边边所在位置的x坐标
        listX = []

        for rect in rectangles:
            listX.append(rect[0])  # 矩形左边边x坐标位置
            listX.append(rect[2])  # 矩形右边边x坐标位置

        # 所有x坐标升序（每个x视为一条扫描线）
        listX.sort()

        # 记录所有矩形并集面积
        ans = 0

        for i in range(1, len(listX)):
            # 前一个扫描线x坐标
            preX = listX[i - 1]
            # 当前扫描线x坐标
            curX = listX[i]

            # 相邻两个扫描线的距离
            width = curX - preX

            # 距离为0, 则跳过
            if width == 0:
                continue

            # 将在[x1,x2]区间上的矩形片段（垂直方向高度区间）收集起来
            lines = []

            # 遍历每个矩形
            # 矩形左下角坐标(x1,y1)，矩形右上角坐标(x2,y2)
            for x1, y1, x2, y2 in rectangles:
                # 如果矩形包含了 [x1, x2] 区间
                if x1 <= preX and curX <= x2:
                    # 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]
                    lines.append((y1, y2))

            # 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序：按照起始位置升序, 如果起始位置相同, 则按照结束位置降序，这样排序的目的是保证排序后，前面的区间尽可能可以覆盖后面的区间
            lines.sort(key=lambda line: (line[0], -line[1]))

            # 记录lines多个区间，求长度之和，（重叠部分只计算一次）
            height = 0

            # 题目说坐标范围 [-100, 100], 因此对应 [?, -101] 的区间必然不会和任何区间相交
            last_end = -1

            # 如果 last_end >= end, 则当前区间被上一个区间完全覆盖，因此可以跳过
            # 如果 last_end < end
            for start, end in lines:
                if last_end < end:
                    # 则当前区间的不重叠部分是 [max(start, last_end), end]
                    height += end - max(start, last_end)
                    # 更新last_end
                    last_end = end

            # 当前扫描线扫描到的面积为 width * height
            ans += width * height

        return ans % 1000000007

JavaScript源码实现

/**
 * @param {number[][]} rectangles
 * @return {number}
 */
var rectangleArea = function (rectangles) {
    // 统计所有矩形的左边边、右边边所在位置的x坐标
    const listX = [];

    for (let rect of rectangles) {
        listX.push(rect[0]); // 矩形左边边x坐标位置
        listX.push(rect[2]); // 矩形右边边x坐标位置
    }

    // 所有x坐标升序（每个x视为一条扫描线）
    listX.sort((a, b) => a - b);

    // 记录所有矩形并集面积
    let ans = 0n;

    for (let i = 1; i < listX.length; i++) {
        // 前一个扫描线x坐标
        const preX = listX[i - 1];
        // 当前扫描线x坐标
        const curX = listX[i];

        // 相邻两个扫描线的距离
        const width = curX - preX;

        // 距离为0, 则跳过
        if (width == 0) continue;

        // 将处于[x1,x2]区间上的矩形片段（垂直方向高度区间）收集起来
        const lines = [];

        // 遍历每个矩形
        // 矩形左下角坐标(x1,y1)，矩形右上角坐标(x2,y2)
        for (let [x1, y1, x2, y2] of rectangles) {
            // 如果矩形有片段处于 [x1, x2] 区间
            if (x1 <= preX && curX <= x2) {
                // 那么该矩形在 水平方向区间[x1, x2] 对应的 垂直方向区间为 [y1, y2]
                lines.push([y1, y2]);
            }
        }

        // 将处于水方向区间 [x1, x2] 的所有垂直方向区间排序：按照起始位置升序, 如果起始位置相同, 则按照结束位置降序，这样排序的目的是保证排序后，前面的区间尽可能可以覆盖后面的区间
        lines.sort((lineA, lineB) =>
            lineA[0] != lineB[0] ? lineA[0] - lineB[0] : lineB[1] - lineA[1]
        );

        // 记录lines多个区间，求长度之和，（重叠部分只计算一次）
        let height = 0;

        let last_end = -1;
        for (let [start, end] of lines) {
            // 如果 last_end >= end, 则当前区间被上一个区间完全覆盖，因此可以跳过
            // 如果 last_end < end
            if (last_end < end) {
                // 则当前区间的不重叠部分是 [max(start, last_end), end]
                height += end - Math.max(start, last_end);
                // 更新last_end
                last_end = end;
            }
        }

        // 当前扫描线扫描到的面积为 width * height
        ans += BigInt(width) * BigInt(height);
    }

    return Number(ans % 1000000007n);
};

原文地址：https://blog.csdn.net/qfc_128220/article/details/142579251

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Linux中的进程替换
下一篇：UE学习篇ContentExample解读------Blueprints Advanced-上

LeetCode 172. 阶乘后的零
给定一个整数 n ，返回 n!结果中尾随零的数量。= 120 ，有一个尾随 0。= 6 ，不含尾随 0。
阅读更多2024-09-28
Redis的过期删除策略
Redis 定期删除策略并不会遍历删除每个过期键，而是采用随机抽取的方式删除过期键，同时为了保证过期扫描不影响 Redis 主业务，Redis 的定期删除策略中还提供了最大执行时间，以保证 Redis
阅读更多2024-09-28
React & 理解 re-render 的作用、概念，并提供详细的例子解释
React & 理解 re-render 的作用、概念，并提供详细的例子解释
阅读更多2024-09-28
C++杂项
将之前实现的顺序表、栈、队列都更改成模板类顺序表运行结果：栈运行结果：队列。
阅读更多2024-09-28
数组三种操作方法的对比
参数修改第一个ChangeIt方法（z = null;）不修改原数组，只改变了局部变量z的引用。方法修改了数组的元素，影响原数组内容。第二个ChangeIt方法通过创建新引用A，也成功修改了原数组的内
阅读更多2024-09-28
前海石公园的停车点探寻
前海石公园是真的很美，很多看海人，很多钓鱼佬，很多抓螃蟹的人，很多挖沙子的人，很多拍照的人，尤其是没有大太阳的时间段或每天傍晚或每个放假的时候人气超高，故前海石公园停车真的很紧张。就在前海石公园停车场
阅读更多2024-09-28
109.游戏安全项目：信息显示二-利用游戏通知辅助计算基址
游戏逆向游戏安全游戏攻防 c++ 反游戏外挂保姆级攻略 Windows
阅读更多2024-09-28
Vue3.X + SpringBoot小程序 | AI大模型项目 | 饮食陪伴官
Food Buddy，饮食陪伴官项目。这是一款专注于饮食管理的uniapp程序。在传统饮食管理APP的基础上，融入了AI伙伴，这个全新的尝试不仅能增加饮食管理的趣味性，更重要的能增加用户解决自身问题
阅读更多2024-09-28
Python Web 与大数据分析平台的集成与应用
在现代数据分析领域，Python凭借其丰富的生态系统，已成为与大数据平台集成的重要工具。大数据平台如Hadoop和Spark为数据存储与处理提供了强大的基础设施，而Python则提供了简洁的编程体验与
阅读更多2024-09-28
Simple Calculator(简单计算器：算法初阶，代码基础，“纯”手撕)
如果你的目标是编写一个易于理解和维护的代码，第一个calculate函数可能更适合。如果你追求代码的简洁性和效率，第二个calculate函数可能更符合你的需求。两个实现都是有效的，并且都可以作为学习
阅读更多2024-09-28