LeetCode 391. 完美矩形

Categories:

题目描述
思路分析
1. 解法一：面积 + 顶点异或（推荐）
相似题目

题目描述

✅ 391. 完美矩形

思路分析

解法一：面积 + 顶点异或（推荐）

核心思路：

完美覆盖需要满足总面积等于外包矩形面积。

使用集合记录角点出现次数，偶数次抵消，最终只剩四个外包角。

同时检查面积一致。

复杂度分析：

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

空间复杂度：O(n)，用于角点集合。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        long area = 0;
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        int maxY = Integer.MIN_VALUE;

        Set<String> set = new HashSet<>();

        for (int[] r : rectangles) {
            int x1 = r[0];
            int y1 = r[1];
            int x2 = r[2];
            int y2 = r[3];

            minX = Math.min(minX, x1);
            minY = Math.min(minY, y1);
            maxX = Math.max(maxX, x2);
            maxY = Math.max(maxY, y2);

            area += (long) (x2 - x1) * (y2 - y1);

            toggle(set, x1, y1);
            toggle(set, x1, y2);
            toggle(set, x2, y1);
            toggle(set, x2, y2);
        }

        long coverArea = (long) (maxX - minX) * (maxY - minY);
        if (area != coverArea) {
            return false;
        }

        if (set.size() != 4) {
            return false;
        }

        return set.contains(key(minX, minY))
                && set.contains(key(minX, maxY))
                && set.contains(key(maxX, minY))
                && set.contains(key(maxX, maxY));
    }

    private void toggle(Set<String> set, int x, int y) {
        String k = key(x, y);
        if (!set.add(k)) {
            set.remove(k);
        }
    }

    private String key(int x, int y) {
        return x + "_" + y;
    }
}

import "fmt"

func isRectangleCover(rectangles [][]int) bool {
	minX, minY := int(1<<60), int(1<<60)
	maxX, maxY := int(-1<<60), int(-1<<60)
	area := int64(0)

	set := make(map[string]bool)

	for _, r := range rectangles {
		x1, y1 := r[0], r[1]
		x2, y2 := r[2], r[3]

		if x1 < minX {
			minX = x1
		}
		if y1 < minY {
			minY = y1
		}
		if x2 > maxX {
			maxX = x2
		}
		if y2 > maxY {
			maxY = y2
		}

		area += int64(x2-x1) * int64(y2-y1)

		toggle(set, x1, y1)
		toggle(set, x1, y2)
		toggle(set, x2, y1)
		toggle(set, x2, y2)
	}

	coverArea := int64(maxX-minX) * int64(maxY-minY)
	if area != coverArea {
		return false
	}

	if len(set) != 4 {
		return false
	}

	if !set[key(minX, minY)] || !set[key(minX, maxY)] || !set[key(maxX, minY)] || !set[key(maxX, maxY)] {
		return false
	}

	return true
}

func toggle(set map[string]bool, x, y int) {
	k := key(x, y)
	if set[k] {
		delete(set, k)
	} else {
		set[k] = true
	}
}

func key(x, y int) string {
	return fmt.Sprintf("%d_%d", x, y)
}

相似题目

题目	难度	考察点
223. 矩形面积	中等	几何
836. 矩形重叠	简单	几何
850. 矩形面积 II	困难	扫描线
218. 天际线问题	困难	扫描线
391. 完美矩形	困难	几何

本文作者: HGNULB

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