leetcode 扫描线专题 06-leetcode.836 rectangle-overlap 力扣.836 矩形重 ...

梦见你的名字 · 2024-11-18 12:59:13

题目

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
矩形的上下边平行于 x 轴，左右边平行于 y 轴。
如果相交的面积为正，则称两矩形重叠。
需要明确的是，只在角或边打仗的两个矩形不构成重叠。
给出两个矩形 rec1 和 rec2。如果它们重叠，返回 true；否则，返回 false 。
示例 1：

输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true

复制代码

示例 2：

输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false

复制代码

示例 3：

输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3]
输出：false

复制代码

提示：
rect1.length == 4
rect2.length == 4

-10^9 rec2[1] && rec1[1] < rec2[3]; // 两个投影都有交集才算重叠 return xOverlap && yOverlap; }}[/code]小结

投影这种解法看起来很简单，实际上很巧妙，但是偶然候我们不见得能想到。
v2-重叠面积

思路

如果两个矩形重叠，那么重叠的面积一定大于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 boolean isRectangleOverlap(int[] rec1, int[] rec2) {
// 判断 x 轴和 y 轴投影是否有交集
boolean xOverlap = rec1[2] > rec2[0] && rec1[0] < rec2[2];
boolean yOverlap = rec1[3] > rec2[1] && rec1[1] < rec2[3];
// 两个投影都有交集才算重叠
return xOverlap && yOverlap;
}
}

复制代码

效果

0ms 100%
小结

这个感觉比方法 1 的投影应该更容易想到一些。
而且可以在后续的 T223 T3047 中拓展利用。
v3-扫描线

扫描线

利用扫描线（sweepline）方法解决这个问题也是一种非经常见且高效的方式。
扫描线的基本思路是将矩形视为一系列的线段，并在 x 轴方向上依次“扫描”这些线段，查抄是否有重叠。
思路

将矩形的边界转换为变乱：
- 每个矩形有 两条边，一个是左边界（x1），一个是右边界（x2）。这两条边界构成了扫描线的“变乱”。
- 对于每个矩形，生成两个变乱：
  - 左边界变乱：表示矩形开始时，增加一个 y 区间（从 y1 到 y2）。
  - 右边界变乱：表示矩形竣事时，移除一个 y 区间（从 y1 到 y2）。
变乱排序：
- 所有的变乱按 x 坐标排序。如果 x 坐标相同，优先处理右边界变乱（因为在同一位置时，应该先移除竣事的矩形，再处理新的开始）。
扫描线处理：
- 扫描线从左到右扫描这些变乱。当扫描到一个 左边界变乱 时，添加相应的 y 区间；当扫描到一个 右边界变乱 时，移除相应的 y 区间。
- 在每次添加或移除变乱时，查抄当前的 y 区间是否存在重叠。如果存在重叠，那么矩形就重叠。
区间重叠查抄：
- 在扫描线过程中，维护一个 活动的 y 区间聚集，该聚集记录了当前所有矩形在 y 轴上的区间。
- 每次添加新的 y 区间时，查抄当前 y 区间是否与已经存在的区间重叠。如果重叠，则说明存在矩形重叠。

具体步调

定义变乱：
- 每个矩形 rec = [x1, y1, x2, y2] 会生成两个变乱：
  - 左边界变乱 (x1, y1, y2, 1) 表示矩形开始（1 表示是左边界）。
  - 右边界变乱 (x2, y1, y2, -1) 表示矩形竣事（-1 表示是右边界）。
排序变乱：
- 按照 x 坐标排序，如果两个变乱的 x 坐标相同，右边界变乱优先。

为什么要这样做？
因为在扫描线的过程中，当我们碰到同一个 x 坐标时，我们希望先处理右边界变乱，再处理左边界变乱。
这是为了制止在处理过程中出现误判的情况。
好比，当一个矩形的右边界和另一个矩形的左边界在同一个 x 坐标上时，我们应该先“移除”第一个矩形的 y 区间，然后再“添加”第二个矩形的 y 区间。

扫描并更新活动区间：
- 用一个数据布局（好比 TreeSet）维护当前的活动区间。每次扫描到一个变乱时，更新该区间，查抄是否存在重叠。

如何判断是否重叠：

public class Solution {
public boolean isRectangleOverlap(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 true;
}
// 没有重叠
return false;
}
}

复制代码

实现

private boolean hasOverlap(TreeSet<int[]> activeIntervals) {
int prevEnd = Integer.MIN_VALUE; // 初始化 prevEnd 为一个极小值
for (int[] interval : activeIntervals) {
// 如果当前区间的起始点小于前一个区间的终点，说明有重叠
if (interval[0] < prevEnd) {
return true; // 有重叠，返回 true
}
prevEnd = interval[1]; // 更新 prevEnd 为当前区间的终点
}
return false; // 如果没有任何重叠，返回 false
}

复制代码

效果

1ms 击败2.08%
小结

整体上而言，我比力喜好重叠面积的方式，这种比力好想到，而且可以扩展。
固然扫描线也是一种很通用的解法。
这一题的巧思属于维度投影的解法，很巧妙。
开源地点

为了便于大家学习，所有实现均已开源。接待 fork + star~

https://github.com/houbb/leetcode

		自动登录	找回密码
密码			立即注册

leetcode 扫描线专题 06-leetcode.836 rectangle-overlap 力扣.836 矩形重 ...

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云