MatrixOverlap题目来源：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对应的list解压赋值给x1,y1,x2,y2；将矩阵rec2对应的list解压赋值给x3,y3,x4,y4。对于rec2大于rec1的情况，说明矩阵rec2在y轴上的最小值大于矩阵rec1在y轴上的最大值。其他三种情况相同，如下表达式：[top]:y3>=y2[rightside]:x3>=x2[bottom]:y4<=y1[leftside]:x4<=x1代码实现类Solution(object):defisRectangleOverlap(self,rec1,rec2):#解压赋值x1,y1,x2,y2=rec1x3,y3,x4,y4=rec2#如果至少满足以下4个条件之一，则meansnon-overlap#题意要求重叠部分，所以returnFalseify3>=y2orx3>=x2ory4<=y1orx1>=x4:returnFalsereturnTrue达到效果以上是到运用逆向思维，考虑两个矩阵如何在相对位置不重叠的情况下，如何逆向求解《矩阵重叠》问题的主要内容。欢迎关注微信公众号《书所集录》
