关于后端:850-矩形面积-II-扫描线模板题

题目形容

这是 LeetCode 上的 850. 矩形面积 II，难度为 艰难。

Tag :「扫描线」

咱们给出了一个（轴对齐的）二维矩形列表 rectangles。对于 $rectangle[i] = [x_1, y_1, x_2, y_2]$，其中 $(x_1, y_1)$ 是矩形 i 左下角的坐标，$ (x_{i1}, y_{i1})$ 是该矩形 左下角 的坐标，$ (x_{i2}, y_{i2})$ 是该矩形 右上角 的坐标。

计算立体中所有 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 <= x_{i1}, y_{i1}, x_{i2}, y_{i2} <= 10^9$
• 矩形叠加笼罩后的总面积不会超过 $2^{63} – 1$，这意味着能够用一个 64 位有符号整数来保留面积后果。

扫描线

这是一道「扫描线」模板题。

将所有给定的矩形的左右边对应的 x 端点提取进去并排序，每个端点可看作是一条竖直的线段（红色），问题转换为求解「由多条竖直线段宰割开」的多个矩形的面积总和（黄色）：

相邻线段之间的宽度为单个矩形的「宽度」（通过 x 差值间接算得），问题转换为求该区间内高度的并集（即矩形的高度）。

因为数据范畴只有 $200$，咱们能够对给定的所有矩形进行遍历，统计所有对该矩形有奉献的 y 值线段（即有哪些 rs[i] 落在该矩形中），再对线段进行求交加（总长度），即可计算出该矩形的「高度」，从而计算出来该矩形的面积。

Java 代码：

class Solution {int MOD = (int)1e9+7;
    public int rectangleArea(int[][] rs) {List<Integer> list = new ArrayList<>();
        for (int[] info : rs) {list.add(info[0]); list.add(info[2]);
        }
        Collections.sort(list);
        long ans = 0;
        for (int i = 1; i < list.size(); i++) {int a = list.get(i - 1), b = list.get(i), len = b - a;
            if (len == 0) continue;
            List<int[]> lines = new ArrayList<>();
            for (int[] info : rs) {if (info[0] <= a && b <= info[2]) lines.add(new int[]{info[1], info[3]});
            }
            Collections.sort(lines, (l1, l2)->{return l1[0] != l2[0] ? l1[0] - l2[0] : l1[1] - l2[1];
            });
            long tot = 0, l = -1, r = -1;
            for (int[] cur : lines) {if (cur[0] > r) {
                    tot += r - l;
                    l = cur[0]; r = cur[1];
                } else if (cur[1] > r) {r = cur[1];
                }
            }
            tot += r - l;
            ans += tot * len;
            ans %= MOD;
        }
        return (int) ans;
    }
}

TypeScript 代码：

const MOD = BigInt(1e9+7)
function rectangleArea(rs: number[][]): number {const list = new Array<number>()
    for (let info of rs) {list.push(info[0]); list.push(info[2]);
    }
    list.sort((a,b)=>a-b)
    let ans = 0n
    for (let i = 1; i < list.length; i++) {const a = list[i - 1], b = list[i], len = b - a
        if (len == 0) continue
        const lines = new Array<number[]>()
        for (let info of rs) {if (info[0] <= a && b <= info[2]) lines.push([info[1], info[3]])
        }
        lines.sort((l1,l2)=>{return l1[0] != l2[0] ? l1[0] - l2[0] : l1[1] - l2[1]
        })
        let tot = 0n, l = -1, r = -1
        for (let cur of lines) {if (cur[0] > r) {tot += BigInt(r - l)
                l = cur[0]; r = cur[1]
            } else if (cur[1] > r) {r = cur[1]
            }
        }
        tot += BigInt(r - l)
        ans += tot * BigInt(len)
        ans %= MOD
    }
    return Number(ans)
};

Python 代码：

class Solution:
    def rectangleArea(self, rs: List[List[int]]) -> int:
        ps = []
        for info in rs:
            ps.append(info[0])
            ps.append(info[2])
        ps.sort()
        ans = 0
        for i in range(1, len(ps)):
            a, b = ps[i - 1], ps[i]
            width = b - a
            if width == 0:
                continue
            lines = [(info[1], info[3]) for info in rs if info[0] <= a and b <= info[2]]
            lines.sort()
            height, l, r = 0, -1, -1
            for cur in lines:
                if cur[0] > r:
                    height += r - l
                    l, r = cur
                elif cur[1] > r:
                    r = cur[1]
            height += r - l
            ans += height * width
        return ans % 1000000007

Go 代码：

const MOD = int64(1e9 + 7)
func rectangleArea(rectangles [][]int) int {list := []int{}
    for _, info := range rectangles {list = append(list, info[0])
        list = append(list, info[2])
    }
    sort.Ints(list)
    ans := int64(0)
    for i := 1; i < len(list); i++ {a, b, length := list[i - 1], list[i], list[i] - list[i - 1]
        if length == 0 {continue}
        lines := [][]int{}
        for _, info := range rectangles {if info[0] <= a && b <= info[2] {lines = append(lines, []int{info[1], info[3]})
            }
        }
        sort.Slice(lines, func(i,j int) bool {if lines[i][0] != lines[j][0] {return lines[i][0] - lines[j][0] < 0
            }
            return lines[i][1] - lines[j][1] < 0
        })
        total, l, r := int64(0), -1, -1
        for _, cur := range lines {if cur[0] > r {total += int64(r - l)
                l, r = cur[0], cur[1]
            } else if cur[1] > r {r = cur[1]
            }
        }
        total += int64(r - l)
        ans += total * int64(length)
        ans %= MOD
    }
    return int(ans)
}

• 工夫复杂度：预处理所有扫描线的复杂度为 $O(n\log{n})$；解决所有相邻的扫描线，并计算相邻扫描线造成的矩形面积复杂度为 $O(n\log{n})$。整体复杂度为 $O(n^2\log{n})$
• 空间复杂度：$O(n)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.850 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布