Easy

题目描述

轴对齐的矩形用列表 [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

约束条件:

  • rec1.length == 4
  • rec2.length == 4
  • -10^9 <= rec1[i], rec2[i] <= 10^9
  • rec1 和 rec2 表示面积不为零的有效矩形

解题思路

判断两个矩形是否重叠有两种主要思路：

方法一：正向判断 直接判断两个矩形是否有重叠区域。两个矩形重叠的条件是：

  1. 在 X 轴方向有重叠：max(x1_1, x1_2) < min(x2_1, x2_2)
  2. 在 Y 轴方向有重叠：max(y1_1, y1_2) < min(y2_1, y2_2)

只有当两个方向都有重叠时，矩形才真正重叠。

方法二：反向判断（推荐） 使用反向思维，判断两个矩形不重叠的情况，然后取反。两个矩形不重叠的情况包括：

  1. rec1 在 rec2 的左边：rec1[2] <= rec2[0]
  2. rec1 在 rec2 的右边：rec1[0] >= rec2[2]
  3. rec1 在 rec2 的下方：rec1[3] <= rec2[1]
  4. rec1 在 rec2 的上方：rec1[1] >= rec2[3]

只要满足任一条件，两矩形就不重叠。反向判断的逻辑更清晰，代码更简洁。

代码实现

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        return !(rec1[2] <= rec2[0] ||   // rec1 在 rec2 左边
                 rec1[0] >= rec2[2] ||   // rec1 在 rec2 右边
                 rec1[3] <= rec2[1] ||   // rec1 在 rec2 下方
                 rec1[1] >= rec2[3]);    // rec1 在 rec2 上方
    }
};

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        return not (rec1[2] <= rec2[0] or   # rec1 在 rec2 左边
                    rec1[0] >= rec2[2] or   # rec1 在 rec2 右边
                    rec1[3] <= rec2[1] or   # rec1 在 rec2 下方
                    rec1[1] >= rec2[3])     # rec1 在 rec2 上方

public class Solution {
    public bool IsRectangleOverlap(int[] rec1, int[] rec2) {
        return !(rec1[2] <= rec2[0] ||   // rec1 在 rec2 左边
                 rec1[0] >= rec2[2] ||   // rec1 在 rec2 右边
                 rec1[3] <= rec2[1] ||   // rec1 在 rec2 下方
                 rec1[1] >= rec2[3]);    // rec1 在 rec2 上方
    }
}

var isRectangleOverlap = function(rec1, rec2) {
    return !(rec1[2] <= rec2[0] ||   // rec1 在 rec2 左边
             rec1[0] >= rec2[2] ||   // rec1 在 rec2 右边
             rec1[3] <= rec2[1] ||   // rec1 在 rec2 下方
             rec1[1] >= rec2[3]);    // rec1 在 rec2 上方
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)只需要进行常数次比较操作
空间复杂度O(1)只使用常数级别的额外空间

相关题目