850. 矩形面積 II : 掃描線模板題

語言: CN / TW / HK

時間 2022-09-17 15:37:48 SegmentFault博客

題目描述

這是 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 。

提示：

掃描線

這是一道「掃描線」模板題。

將所有給定的矩形的左右邊對應的 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 道題目，部分是有鎖題，我們將先把所有不帶鎖的題目刷完。

在這個系列文章裏面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模板。

為了方便各位同學能夠電腦上進行調試和提交代碼，我建立了相關的倉庫： http://github.com/SharingSou... 。

在倉庫地址裏，你可以看到系列文章的題解鏈接、系列文章的相應代碼、LeetCode 原題鏈接和其他優選題解。

更多更全更熱門的「筆試/面試」相關資料可訪問排版精美的合集新基地 :tada::tada:

本文由mdnice多平台發佈

「其他文章」