力扣.223 矩形面积 rectangle-area

题目

给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你盘算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 极点和 右上 极点坐标体现：
第一个矩形由其左下极点 (ax1, ay1) 和右上极点 (ax2, ay2) 定义。
第二个矩形由其左下极点 (bx1, by1) 和右上极点 (bx2, by2) 定义。
示例 1：
Rectangle Area
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出：45
示例 2：
输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出：16
提示：
-10^4  0，否则交集的面积为 0。
结果

完整的面积 = 两个矩形面积之和 - 重叠面积
代码示例

1. class Solution {
2.     public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
3.         int rect1 = rectangleArea(ax1, ay1, ax2, ay2);
4.         int rect2 = rectangleArea(bx1, by1, bx2, by2);
6.         int overlap = rectangleOverlapArea(new int[]{ax1, ay1, ax2, ay2}, new int[]{bx1, by1, bx2, by2});
8.         return rect1-overlap+rect2;
9.     }
11.     private int rectangleArea(int ax1, int ay1, int ax2, int ay2) {
12.         return (ax2-ax1) * (ay2-ay1);
13.     }
15.     public int rectangleOverlapArea(int[] rec1, int[] rec2) {
16.         // 计算交集矩形的左下角和右上角
17.         int x1 = Math.max(rec1[0], rec2[0]);
18.         int y1 = Math.max(rec1[1], rec2[1]);
19.         int x2 = Math.min(rec1[2], rec2[2]);
20.         int y2 = Math.min(rec1[3], rec2[3]);
22.         // 计算交集的宽度和高度
23.         int width = x2 - x1;
24.         int height = y2 - y1;
26.         // 如果交集的宽度和高度都大于 0，说明有重叠
27.         if (width > 0 && height > 0) {
28.             return width * height;
29.         }
31.         // 没有重叠
32.         return 0;
33.     }
34. }

复制代码

效果

2ms 击败21.43%
小结

这种解法相对对比较天然。
v2-扫描线

思路

按照 x 轴，将整体的矩形面积，按照每一段 x 拆分为小矩形。
末了的和就是整体矩形之和。
解法

[code]public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {    int[][] arr = new int[2][];    arr[0] = new int[]{ax1, ay1, ax2, ay2};    arr[1] = new int[]{bx1, by1, bx2, by2};    Arrays.sort(arr, (o1, o2) -> o1[1] == o2[1] ? o1[3] - o2[3] : o1[1] - o2[1]);    List xList = Arrays.asList(ax1, ax2, bx1, bx2);    Collections.sort(xList);    int ans = 0;    for (int i = 1; i < 4; i++) {        int width = xList.get(i) - xList.get(i-1);        for (int[] ints : getLine(xList.get(i-1), xList.get(i), arr)) {            ans += width * (ints[1] - ints[0]);        }    }    return ans;}private List getLine(int x1, int x2, int[][] arr) {    List list = new ArrayList();    for (int[] ints : arr) {        if (x1 >= ints[0] && x2