矩阵重叠
题目来源：
https://leetcode-cn.com/problems/rectangle-overlap/
题目
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形，判断它们是否重叠并返回结果。
示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true
示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false
提示：
-
两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
-
矩形中的所有坐标都处于 -10^9 和 10^9 之间。
-
x 轴默认指向右，y 轴默认指向上。
-
你可以仅考虑矩形是正放的情况。
解题思路
思路：逆向思维，检查两个矩阵的相对位置。
虽然本题要求的是两个矩阵是否有重叠的部分，但同时可以反过来思考，两个矩阵在什么情况下不会重叠。那么排除不重叠的情况，那剩下的则是重叠的情况。
在本题中，可以考虑两个矩阵的相对位置。假设先固定其中一个矩阵
rec1
，现在考虑在什么情况下，另外一个矩阵
rec2
不会与当前矩阵重叠。
当
rec1
固定时，只要
rec2
出现在
rec1
的四个方向，也就是说，满足下面的至少一种，则两者不会重叠：
-
rec2
在
rec1
的上方；
-
rec2
在
rec1
的右侧；
-
rec2
在
rec1
的下方；
-
rec2
在
rec1
的左侧。
在这里，具体如何定义四个方向？【上方】表示的是，可以找到一条平行于 x 轴的线（这里线可以跟矩阵的边重合，题目有提及）将两个矩阵分隔开。【右侧】、【下方】和【左侧】同理。
现在已经可以明确，只要出现上面情况中至少一种，两个矩阵都不会重合。那么现在考虑，如何将这四种情况，转换为明确的表达式。
根据题意，矩阵是以列表
[x1, y1, x2, y2]
的形式表示，其中
(x1, y1)
为左下角的坐标，
(x2, y2)
是右上角的坐标。
那么先将矩阵
rec1
对应的列表，解压赋值给
x1, y1, x2, y2
；将矩阵
rec2
对应的列表，解压赋值给
x3, y3, x4, y4
。
对于
rec2
在
rec1
的上方这种情况，表示矩阵
rec2
在 y 轴上的最小值，要大于矩阵
rec1
在 y 轴上的最大值。另外三种情况同理，如下面的表达式：
-
【上方】：
y3 >= y2
-
【右侧】：
x3 >= x2
-
【下方】：
y4 <= y1
-
【左侧】：
x4 <= x1
代码实现
class Solution(object):
def isRectangleOverlap(self, rec1, rec2):
# 解压赋值
x1, y1, x2, y2 = rec1
x3, y3, x4, y4 = rec2
# 符合下面 4 中情况的至少一种就表示不重合
# 题意要求重叠部分，这里不重合所以返回 False
if y3 >= y2 or x3 >= x2 or y4 <= y1 or x1 >= x4:
return False
return True
实现效果
以上就是使用逆向思维，考虑两个矩阵相对位置如何不重叠的情况逆向解决《矩阵重叠》问题的主要内容。
欢迎关注微信公众号《书所集录》
