836.矩形重叠

LeetCode LeetCode 数学几何

发布时间 : 2000-01-10 08:03

字数:1.6k 阅读 :

评论:

836.矩形重叠

836.矩形重叠

836.1 题目

矩形以列表 [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 <= rec1[i], rec2[i] <= 10^9
rec1 和 rec2 表示一个面积不为零的有效矩形

836.2 题解

方法一：区间投影法

思路

把二维问题降维：矩形重叠 = x轴投影重叠且 y轴投影重叠。

区间重叠的条件：max(起点1, 起点2) < min(终点1, 终点2)

举个例子：rec1 = [0,0,2,2], rec2 = [1,1,3,3]

x轴：rec1是[0,2]，rec2是[1,3]
max(0,1)=1 < min(2,3)=2，x轴重叠 ✓
y轴：rec1是[0,2]，rec2是[1,3]
max(0,1)=1 < min(2,3)=2，y轴重叠 ✓
两轴都重叠，返回 true

举个例子：rec1 = [0,0,1,1], rec2 = [1,0,2,1]

x轴：[0,1] 和 [1,2]
max(0,1)=1 < min(1,2)=1？不成立！
x轴不重叠，返回 false

复杂度分析

时间复杂度：O(1)
空间复杂度：O(1)

代码

// 方法一：区间投影法
// 检查两个矩形在x和y的投影是否相交，通过比较最大起点是否小于最小终点判断
static bool IsRectangleOverlap1(int[] rec1, int[] rec2)
{
    // 检查 x 轴投影是否相交
    bool xOverlap = CheckOverlap(rec1[0], rec1[2], rec2[0], rec2[2]);
    // 检查 y 轴投影是否相交
    bool yOverlap = CheckOverlap(rec1[1], rec1[3], rec2[1], rec2[3]);
    // 如果 x 轴和 y 轴投影都相交，则矩形重叠
    return xOverlap && yOverlap;
}

// 检查投影是否相交
static bool CheckOverlap(int start1, int end1, int start2, int end2)
{
    // 通过比较最大起点和最小终点来检查两个区间在数轴上是否有重叠
    return Math.Max(start1, start2) < Math.Min(end1, end2);
}

方法二：边界判断法

思路

从反面思考：什么情况下矩形不重叠？

不重叠的四种情况：

rec1 在 rec2 左边：rec1右边界 ≤ rec2左边界
rec1 在 rec2 右边：rec1左边界 ≥ rec2右边界
rec1 在 rec2 上面：rec1下边界 ≥ rec2上边界
rec1 在 rec2 下面：rec1上边界 ≤ rec2下边界

如果以上四种情况都不满足，则重叠。

举个例子：rec1 = [0,0,1,1], rec2 = [1,0,2,1]

rec1右边界=1 ≤ rec2左边界=1？是的！
所以 rec1 在 rec2 左边，不重叠

复杂度分析

时间复杂度：O(1)
空间复杂度：O(1)

代码

// 方法二：边界判断法
// 判断矩形1是否在矩形2的左侧、右侧、上方和下方，如果都不在说明重叠
static bool IsRectangleOverlap2(int[] rec1, int[] rec2)
{
    // 检查 rec1 在 rec2 的左侧、右侧、上方和下方
    bool isLeft = rec1[2] <= rec2[0];
    bool isRight = rec1[0] >= rec2[2];
    bool isAbove = rec1[1] >= rec2[3];
    bool isBelow = rec1[3] <= rec2[1];

    // 如果都不在说明重叠
    return !(isLeft || isRight || isAbove || isBelow);
}

836.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 矩形以列表 [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
        // -109 <= rec1[i], rec2[i] <= 109
        // rec1 和 rec2 表示一个面积不为零的有效矩形

        #endregion

        #region 测试

        // 示例 1
        int[] rec1_1 = { 0, 0, 2, 2 };
        int[] rec2_1 = { 1, 1, 3, 3 };
        bool result1_1 = IsRectangleOverlap1(rec1_1, rec2_1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        bool result1_2 = IsRectangleOverlap2(rec1_1, rec2_1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] rec1_2 = { 0, 0, 1, 1 };
        int[] rec2_2 = { 1, 0, 2, 1 };
        bool result2_1 = IsRectangleOverlap1(rec1_2, rec2_2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        bool result2_2 = IsRectangleOverlap2(rec1_2, rec2_2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int[] rec1_3 = { 0, 0, 1, 1 };
        int[] rec2_3 = { 2, 2, 3, 3 };
        bool result3_1 = IsRectangleOverlap1(rec1_3, rec2_3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");
        bool result3_2 = IsRectangleOverlap2(rec1_3, rec2_3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：区间投影法
    // 检查两个矩形在x和y的投影是否相交，通过比较最大起点是否小于最小终点判断
    static bool IsRectangleOverlap1(int[] rec1, int[] rec2)
    {
        // 检查 x 轴投影是否相交
        bool xOverlap = CheckOverlap(rec1[0], rec1[2], rec2[0], rec2[2]);
        // 检查 y 轴投影是否相交
        bool yOverlap = CheckOverlap(rec1[1], rec1[3], rec2[1], rec2[3]);
        // 如果 x 轴和 y 轴投影都相交，则矩形重叠
        return xOverlap && yOverlap;
    }

    // 检查投影是否相交
    static bool CheckOverlap(int start1, int end1, int start2, int end2)
    {
        // 通过比较最大起点和最小终点来检查两个区间在数轴上是否有重叠
        return Math.Max(start1, start2) < Math.Min(end1, end2);
    }

    // 方法二：边界判断法
    // 判断矩形1是否在矩形2的左侧、右侧、上方和下方，如果都不在说明重叠
    static bool IsRectangleOverlap2(int[] rec1, int[] rec2)
    {
        // 检查 rec1 在 rec2 的左侧、右侧、上方和下方
        bool isLeft = rec1[2] <= rec2[0];
        bool isRight = rec1[0] >= rec2[2];
        bool isAbove = rec1[1] >= rec2[3];
        bool isBelow = rec1[3] <= rec2[1];

        // 如果都不在说明重叠
        return !(isLeft || isRight || isAbove || isBelow);
    }

    #endregion
}

836.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
示例3 方法1 输出：False
示例3 方法2 输出：False

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com