不规则图形面积的两种算法（教3妹学算法矩形面积）

#创作挑战赛#

3妹

3妹：2哥，台风梅花今天夜里要登陆上海了，今天下午已经登陆浙江了。2哥：是啊，风力14级，还是很强的，你看现在都下大雨刮大风了。3妹：据说将是1950年以来登陆上海的最大台风。2哥：恩，下这么大的雨，晚上就不出去吃饭了，还要关好门窗。3妹：那晚饭吃什么，吃红烧牛肉的还是香菇炖鸡的？2哥：还是给我来个老坛酸菜的吧。3妹：切，时间还早，我先刷道算法题再吃。2哥：那我也来一道算法题当开胃菜。

讲课

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

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

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

示例 1：

image.png

输入：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 <= 200rectanges[i].length = 40 <= xi1, yi1, xi2, yi2 <= 109矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。

class Solution { public int rectangleArea(int[][] rectangles) { int N = rectangles.length; Set<Integer> Xvals = new HashSet(); Set<Integer> Yvals = new HashSet(); for (int[] rec: rectangles) { Xvals.add(rec[0]); Xvals.add(rec[2]); Yvals.add(rec[1]); Yvals.add(rec[3]); } Integer[] imapx = Xvals.toArray(new Integer[0]); Arrays.sort(imapx); Integer[] imapy = Yvals.toArray(new Integer[0]); Arrays.sort(imapy); Map<Integer, Integer> mapx = new HashMap(); Map<Integer, Integer> mapy = new HashMap(); for (int i = 0; i < imapx.length; i) mapx.put(imapx[i], i); for (int i = 0; i < imapy.length; i) mapy.put(imapy[i], i); boolean[][] grid = new boolean[imapx.length][imapy.length]; for (int[] rec: rectangles) for (int x = mapx.get(rec[0]); x < mapx.get(rec[2]); x) for (int y = mapy.get(rec[1]); y < mapy.get(rec[3]); y) grid[x][y] = true; long ans = 0; for (int x = 0; x < grid.length; x) for (int y = 0; y < grid[0].length; y) if (grid[x][y]) ans = (long) (imapx[x 1] - imapx[x]) * (imapy[y 1] - imapy[y]); ans %= 1_000_000_007; return (int) ans; } }