LeetCode 850. 矩形面积 II

Categories:

题目描述
思路分析
1. 解法一：扫描线 + 线段树（推荐）
相似题目

题目描述

✅ 850. 矩形面积 II

思路分析

解法一：扫描线 + 线段树（推荐）

核心思路：

对每个矩形生成两条竖边事件，按 x 排序扫描。

线段树维护当前 x 段内被覆盖的 y 总长度。

相邻事件的 x 差乘以当前覆盖长度累加面积。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示矩形数量。

空间复杂度：O(n)。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    private static final int MOD = 1_000_000_007;

    public int rectangleArea(int[][] rectangles) {
        List<int[]> events = new ArrayList<>();
        List<Integer> ys = new ArrayList<>();

        for (int[] r : rectangles) {
            events.add(new int[]{r[0], r[1], r[3], 1});
            events.add(new int[]{r[2], r[1], r[3], -1});
            ys.add(r[1]);
            ys.add(r[3]);
        }

        ys.sort(Integer::compareTo);
        List<Integer> uniq = new ArrayList<>();
        for (int y : ys) {
            if (uniq.isEmpty() || uniq.get(uniq.size() - 1) != y) {
                uniq.add(y);
            }
        }

        int[] coords = new int[uniq.size()];
        for (int i = 0; i < uniq.size(); i++) {
            coords[i] = uniq.get(i);
        }

        events.sort(Comparator.comparingInt(a -> a[0]));
        SegmentTree tree = new SegmentTree(coords);

        long area = 0;
        int prevX = events.get(0)[0];
        for (int[] e : events) {
            int x = e[0];
            long cover = tree.totalLen();
            area = (area + cover * (x - prevX)) % MOD;

            int y1 = e[1];
            int y2 = e[2];
            int type = e[3];
            int l = Arrays.binarySearch(coords, y1);
            int r = Arrays.binarySearch(coords, y2);
            tree.update(l, r, type, 1, 0, coords.length - 1);

            prevX = x;
        }

        return (int) area;
    }

    private static class SegmentTree {
        private final int[] ys;
        private final int[] count;
        private final long[] len;

        SegmentTree(int[] ys) {
            this.ys = ys;
            int n = ys.length * 4;
            this.count = new int[n];
            this.len = new long[n];
        }

        long totalLen() {
            return len[1];
        }

        void update(int ql, int qr, int val, int idx, int l, int r) {
            if (ql >= r || qr <= l) {
                return;
            }
            if (ql <= l && r <= qr) {
                count[idx] += val;
                pushUp(idx, l, r);
                return;
            }

            int mid = (l + r) / 2;
            update(ql, qr, val, idx * 2, l, mid);
            update(ql, qr, val, idx * 2 + 1, mid, r);
            pushUp(idx, l, r);
        }

        void pushUp(int idx, int l, int r) {
            if (count[idx] > 0) {
                len[idx] = ys[r] - ys[l];
                return;
            }
            if (l + 1 >= r) {
                len[idx] = 0;
                return;
            }
            len[idx] = len[idx * 2] + len[idx * 2 + 1];
        }
    }
}

import (
	"sort"
)

func rectangleArea(rectangles [][]int) int {
	const mod int64 = 1_000_000_007
	type event struct {
		x   int
		y1  int
		y2  int
		typ int
	}

	events := make([]event, 0)
	ys := make([]int, 0)

	for _, r := range rectangles {
		events = append(events, event{x: r[0], y1: r[1], y2: r[3], typ: 1})
		events = append(events, event{x: r[2], y1: r[1], y2: r[3], typ: -1})
		ys = append(ys, r[1], r[3])
	}

	sort.Ints(ys)
	coords := make([]int, 0)
	for _, y := range ys {
		if len(coords) == 0 || coords[len(coords)-1] != y {
			coords = append(coords, y)
		}
	}

	sort.Slice(events, func(i, j int) bool { return events[i].x < events[j].x })
	seg := newSegTree(coords)

	area := int64(0)
	prevX := events[0].x
	for _, e := range events {
		x := e.x
		cover := seg.totalLen()
		area = (area + cover*int64(x-prevX)) % mod

		l := sort.SearchInts(coords, e.y1)
		r := sort.SearchInts(coords, e.y2)
		seg.update(l, r, e.typ, 1, 0, len(coords)-1)

		prevX = x
	}

	return int(area)
}

type segTree struct {
	ys    []int
	count []int
	len   []int64
}

func newSegTree(ys []int) *segTree {
	n := len(ys) * 4
	return &segTree{ys: ys, count: make([]int, n), len: make([]int64, n)}
}

func (t *segTree) totalLen() int64 {
	return t.len[1]
}

func (t *segTree) update(ql int, qr int, val int, idx int, l int, r int) {
	if ql >= r || qr <= l {
		return
	}
	if ql <= l && r <= qr {
		t.count[idx] += val
		t.pushUp(idx, l, r)
		return
	}
	mid := (l + r) / 2
	t.update(ql, qr, val, idx*2, l, mid)
	t.update(ql, qr, val, idx*2+1, mid, r)
	t.pushUp(idx, l, r)
}

func (t *segTree) pushUp(idx int, l int, r int) {
	if t.count[idx] > 0 {
		t.len[idx] = int64(t.ys[r] - t.ys[l])
		return
	}
	if l+1 >= r {
		t.len[idx] = 0
		return
	}
	t.len[idx] = t.len[idx*2] + t.len[idx*2+1]
}

相似题目

题目	难度	考察点
218. 天际线问题	困难	扫描线
391. 完美矩形	困难	扫描线
253. 会议室 II	中等	扫描线
56. 合并区间	中等	区间
699. 掉落的方块	困难	线段树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/96547520