当前位置：首页 > article >正文

力扣.223 矩形面积 rectangle-area

article 2024/11/20 20:53:29

题目

给你二维平面上两个由直线构成且边与坐标轴平行/垂直的矩形，请你计算并返回两个矩形覆盖的总面积。

每个矩形由其左下顶点和右上顶点坐标表示：

第一个矩形由其左下顶点 (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 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 10^4

v1-重叠面积

思路

如果矩形不重叠，就是 2 个矩形的面积之和。

如果重合，计算出重叠面积，就是原始的面积之和-重叠面积。

如果两个矩形重叠，那么重叠的面积一定大于0.

于是问题变成如何计算重叠的矩形面积？

如果有重叠，重叠的部分也一定是一个矩形

交集面积的计算方式是基于两个矩形的重叠区域的 左下角和右上角的坐标 来推算的。

具体来说，两个矩形的交集矩形（如果存在）也是一个矩形，它的边界由两个矩形的边界决定。

计算重叠面积

第一个矩形 rec1 = [x1, y1, x2, y2]，表示其左下角坐标为 (x1, y1)，右上角坐标为 (x2, y2)。
第二个矩形 rec2 = [x3, y3, x4, y4]，表示其左下角坐标为 (x3, y3)，右上角坐标为 (x4, y4)。

如果两个矩形有交集，那么交集的矩形的左下角和右上角的坐标可以通过取两者的最大和最小值来确定：

交集矩形的左下角：(x1', y1') = (max(x1, x3), max(y1, y3))
交集矩形的右上角：(x2', y2') = (min(x2, x4), min(y2, y4))

判断交集是否存在

交集矩形的面积只有在其宽度和高度都大于 0 时才存在。

如果交集矩形的宽度或高度小于等于 0，说明两个矩形没有交集。

因此，交集矩形的宽度和高度的计算方式如下：

宽度：width = x2' - x1'
高度：height = y2' - y1'

交集矩形的面积则为：

面积 = width * height，但是如果宽度或高度小于等于 0，面积就为 0。

因此，计算交集的面积时，我们需要确保 width > 0 和 height > 0，否则交集的面积为 0。

结果

完整的面积 = 两个矩形面积之和 - 重叠面积

代码示例

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int rect1 = rectangleArea(ax1, ay1, ax2, ay2);
        int rect2 = rectangleArea(bx1, by1, bx2, by2);

        int overlap = rectangleOverlapArea(new int[]{ax1, ay1, ax2, ay2}, new int[]{bx1, by1, bx2, by2});

        return rect1-overlap+rect2;
    }

    private int rectangleArea(int ax1, int ay1, int ax2, int ay2) {
        return (ax2-ax1) * (ay2-ay1);
    }

    public int rectangleOverlapArea(int[] rec1, int[] rec2) {
        // 计算交集矩形的左下角和右上角
        int x1 = Math.max(rec1[0], rec2[0]);
        int y1 = Math.max(rec1[1], rec2[1]);
        int x2 = Math.min(rec1[2], rec2[2]);
        int y2 = Math.min(rec1[3], rec2[3]);

        // 计算交集的宽度和高度
        int width = x2 - x1;
        int height = y2 - y1;

        // 如果交集的宽度和高度都大于 0，说明有重叠
        if (width > 0 && height > 0) {
            return width * height;
        }

        // 没有重叠
        return 0;
    }
}

效果

2ms 击败21.43%

小结

这种解法相对对比较自然。

v2-扫描线

思路

按照 x 轴，将整体的矩形面积，按照每一段 x 拆分为小矩形。

最后的和就是整体矩形之和。

解法

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<Integer> 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<int[]> getLine(int x1, int x2, int[][] arr) {
    List<int[]> list = new ArrayList<>();
    for (int[] ints : arr) {
        if (x1 >= ints[0] && x2 <= ints[2]) {
            if (list.isEmpty()) {
                list.add(new int[]{ints[1], ints[3]});
            } else {
                int[] tmp = list.get(list.size() - 1);
                if (tmp[1] < ints[1]) {
                    list.add(new int[]{ints[1], ints[3]});
                } else if (tmp[1] < ints[3]) {
                    tmp[1] = ints[3];
                }
            }
        }
    }
    return list;
}