Skip to content

850. Rectangle Area II

850. Rectangle Area II

题目: https://leetcode.com/problems/rectangle-area-ii/

难度: Hard

题意:

  1. 给n个矩阵,求这n个矩阵覆盖的区域面积有多大

思路:

  • 把x坐标和y坐标id化,将n个矩阵覆盖的区域分成r*c个小矩阵,这些小矩阵的距离都可以不相等
  • 遍历所有的矩阵,把这些小矩阵填充满
  • 遍历小矩阵,统计面积
  • 复杂度是o(n^3)
  • 这个题目可以将x坐标id化后,构建线段树来查询和更新面积区域,复杂度可以降为o(n^2logn),当n>=1000使用

代码:

class Solution {
     private int[] setToArray(TreeSet<Integer> set) {
        int[] ret = new int[set.size()];
        int idx = 0;
        for (Integer e: set) {
            ret[idx++] = e;
        }
        return ret;
    }

    private static int MOD = 1000000007;

    public int rectangleArea(int[][] rectangles) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 0;i < rectangles.length;i++) {
            set.add(rectangles[i][0]);
            set.add(rectangles[i][2]);
        }
        int[] x = setToArray(set);

        set.clear();
        for (int i = 0;i < rectangles.length;i++) {
            set.add(rectangles[i][1]);
            set.add(rectangles[i][3]);
        }
        int[] y = setToArray(set);

        boolean[][] area = new boolean[x.length][y.length];
        for (int i = 0;i < x.length;i++) {
            for (int j = 0;j < y.length;j++) {
                area[i][j] = false;
            }
        }
        for (int i = 0;i < rectangles.length;i++) {
            int lx = Arrays.binarySearch(x, rectangles[i][0]);
            int rx = Arrays.binarySearch(x, rectangles[i][2]);

            int ly = Arrays.binarySearch(y, rectangles[i][1]);
            int ry = Arrays.binarySearch(y, rectangles[i][3]);

            for (int j = lx;j < rx;j++) {
                for (int k = ly;k < ry;k++) {
                    area[j][k] = true;
                }
            }
        }
        int ret = 0;
        for (int i = 0;i < x.length;i++) {
            for (int j = 0;j < y.length;j++) {
                if (area[i][j]) {
                    ret += (long)(x[i + 1] - x[i]) * (y[j + 1] - y[j]) % MOD;
                    if (ret >= MOD) {
                        ret -= MOD;
                    }
                }
            }
        }
        return ret;
    }
}


回到顶部