836.矩形重叠

解题思路

解法一：逆向思维

直接证明两个矩形相交的情况会有很多种，所以可以逆向考虑两个矩形不相交的情形。不妨假设固定矩形 rec1，如果矩形rec2与rec1不相交，则rec2在rec1的四周，也就是说至少满足以下四种情况中的一种：
rec2在rec1的左边
rec2在rec1的右边
rec2在rec1的上边
rec2在rec1的下边
对于rec2在rec1的左边而言，即rec2在x轴上的最大值不能大于rec1在x轴上的最小值，也即rec2[2]<=rec1[0]，其他情形类比可得。

复杂度分析：
时间复杂度：O(1)。
空间复杂度：O(1)，不需要额外的空间。

解法二：数学思想

两个矩形重叠，则其水平边在x轴上的投影和竖直边在y轴上的投影必然都有交集，rec1的水平边为(rec1[0], rec1[2])，竖直边为(rec1[1], rec1[3])；rec2的水平边为(rec2[0], rec2[2])，竖直边为(rec2[1], rec2[3])。数学上，判断 (a,b)与(c,d)是否有交集，除了可以用逆向思维先判断不相交的情形，也可以直接判断是否相交，即两条边中右端点的最小值大于两条边中左端点的最大值，min(b,d) > max(a,c),

复杂度分析：
时间复杂度：O(1)。
空间复杂度：O(1)，不需要额外的空间。

代码

解法一： 逆向思维

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

解法二：数学思想

class Solution:
    def isOverlap(self, a,b,c,d):
        if min(b,d)>max(a,c):
            return True
        else:
            return False
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
        return (self.isOverlap(rec1[0],rec1[2],rec2[0],rec2[2]) and self.isOverlap(rec1[1],rec1[3],rec2[1],rec2[3]))