leetcode
leetcode 751 ~ 800
矩形重叠

矩形重叠

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 15.9 MB


/*
 * 使用Java Stream的解法
 * 1. 两个矩形相交的条件是一个矩形的右边不能在另一个矩形的左边,
 *    一个矩形的左边不能在另一个矩形的右边,一个矩形的上边不能在另一个矩形的下边,
 *    一个矩形的下边不能在另一个矩形的上边。
 * 2. 如果这些条件都不满足,那么矩形就是重叠的。
 */
import java.util.stream.IntStream;

public class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // 使用stream流来检查矩形是否相交
        return IntStream.of(rec1[2], rec1[0], rec1[3], rec1[1])
                .noneMatch(i -> i <= rec2[0] || i >= rec2[2] || i <= rec2[1] || i >= rec2[3]);
    }
}

解释

方法:

此题解的思路是通过判断两个矩形是否在水平或垂直方向上完全分离来确定它们是否重叠。对于两个矩形 rec1 和 rec2,它们分别由两个对角顶点坐标 (x1, y1, x2, y2) 和 (x3, y3, x4, y4) 定义。通过比较这些顶点的坐标,我们可以轻松判断出这两个矩形是否在任何一个方向上分离: 1. 如果 rec1 在 rec2 的左侧或右侧则不重叠,即当 x1 >= x4 或 x3 >= x2。 2. 如果 rec1 在 rec2 的上方或下方则不重叠,即当 y1 >= y4 或 y3 >= y2。 只有当这两个条件都不满足时,即矩形在水平和垂直方向上都存在重叠,我们才认为两个矩形重叠。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在判断两个矩形是否重叠时,只考虑了x和y轴方向的分离条件,而没有考虑对角线方向的任何条件?
在矩形的几何属性中,矩形的边总是与坐标轴平行或垂直。因此,两个矩形是否重叠可以完全通过它们在x轴和y轴上的投影来判断。如果两个矩形在x轴或y轴的投影都不重叠,那么这两个矩形在二维空间中也不会重叠。对角线方向的条件不需要单独考虑,因为它不会影响矩形在水平或垂直方向上的重叠情况。
🦆
在算法中提到如果`x1 >= x4 or x3 >= x2`则两矩形不重叠,这个条件是否考虑了矩形边界重合的情况?即是否包括边界接触也认为是不重叠?
是的,这个条件考虑了矩形边界重合的情况。在这种情况下,如果两个矩形的边缘恰好对齐(即x1等于x4或x3等于x2),它们在水平方向上没有内部空间重叠,因此被视为不重叠。这种定义通常用于处理矩形重叠的问题,确保仅当两个矩形在水平或垂直方向上有实际重叠时,才认为它们重叠。
🦆
题解中提到,如果`y1 >= y4 or y3 >= y2`则表示一个矩形在另一个矩形的上方或下方,这里的比较逻辑是否可以处理所有的垂直非重叠情况?
是的,这个逻辑可以处理所有的垂直非重叠情况。这种判断方式确保了如果一个矩形完全在另一个矩形的上方或下方,它们在垂直方向上不会重叠。这里同样包括了边界接触的情况,即如果一个矩形的底部恰好与另一个矩形的顶部对齐,也被视为不重叠。
🦆
在进行坐标比较时,是否需要考虑矩形的坐标点输入顺序可能不一致(例如矩形可能以右上角和左下角的顺序给出)?
实际上,这个问题非常关键。通常,我们假设矩形的坐标是以规范的方式给出的,即第一个点是左下角,第二个点是右上角。如果坐标点的输入顺序不一致,我们需要在算法实现中先处理这些坐标,确保它们是规范的。这可能涉及到对每个矩形的坐标进行排序或调整,以确保x1、y1总是小于或等于x2、y2,这样才能正确地应用重叠判断逻辑。

相关问题

矩形面积

给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形,请你计算并返回两个矩形覆盖的总面积。

每个矩形由其 左下 顶点和 右上 顶点坐标表示:

  • 第一个矩形由其左下顶点 (ax1, ay1) 和右上顶点 (ax2, ay2) 定义。
  • 第二个矩形由其左下顶点 (bx1, by1) 和右上顶点 (bx2, by2) 定义。

 

示例 1:

Rectangle Area
输入:ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
输出:45

示例 2:

输入:ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
输出:16

 

提示:

  • -104 <= ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 <= 104