LeetCode 836. 矩形重叠

◎

本节目标

将轴对齐矩形的正面积相交拆成两个一维严格重叠条件。

查看原题

返回博弈与计算几何框架

题意与约束

两个轴对齐矩形由 [x1, y1, x2, y2] 给出，判断它们是否有正面积重叠；共享边或顶点不算。

第一反应与瓶颈

枚举内部点既不适合连续坐标，也把常数判断做成了网格问题。二维的难处实际上只来自两个互相独立的轴。

数学关系与算法推导

两个一维区间严格重叠，当且仅当较大左端点小于较小右端点。矩形有正面积交集，当且仅当 x 投影和 y 投影都满足该条件：max(x1) < min(x2) 且 max(y1) < min(y2)。

正确性依据

若任一轴投影没有正长度交集，二维交集的该维长度为零，面积不可能为正。反之，两个轴各有正长度公共区间，它们的笛卡尔积就是一块正面积的公共矩形。

样例执行过程

[0,0,2,2] 与 [1,1,3,3] 在两个轴上的公共区间都是 [1,2]，所以重叠。若第二个矩形从 x=1 才开始而第一个也在 x=1 结束，公共长度为零。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        return max(rec1[0], rec2[0]) < min(rec1[2], rec2[2])
            && max(rec1[1], rec2[1]) < min(rec1[3], rec2[3]);
    }
};

Python

Python 3

class Solution:
    def isRectangleOverlap(self, rec1: list[int], rec2: list[int]) -> bool:
        return (
            max(rec1[0], rec2[0]) < min(rec1[2], rec2[2])
            and max(rec1[1], rec2[1]) < min(rec1[3], rec2[3])
        )

复杂度分析

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

边界与易错点

• 比较必须是严格 <，不能写成 <=。
• 完全包含同样满足两个投影严格重叠。
• 只读取坐标，不修改平台传入的数组。

模式迁移

轴对齐的二维、三维盒体相交都可以先做各坐标轴投影；更高维时依然要求每一维都有正长度交集。