836. 矩形重叠
题目描述
每个矩形用数组 [x1, y1, x2, y2] 表示，(x1, y1) 是左下角坐标，(x2, y2) 是右上角坐标。矩形的边都与坐标轴平行。
两个矩形的公共部分面积大于 0 时才算重叠。只有边或顶点接触时，公共面积为 0，不算重叠。
输入两个矩形 rec1 和 rec2，重叠返回 true，否则返回 false。
示例 1
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 输出：true
解释：两者共有边长为 1 的正方形区域 [1,1] 到 [2,2]。
示例 2
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1] 输出：false
解释：两个矩形只共用 x = 1 这条边，面积为 0。
示例 3
输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3] 输出：false
解释：两个矩形完全分离。
数据范围
rect1.length == 4rect2.length == 4-10^9 <= rec1[i], rec2[i] <= 10^9rec1和rec2都是面积大于 0 的合法矩形。
解题思路：投影区间求交
把二维问题拆成两个一维问题：两个矩形重叠，当且仅当它们在 x 轴上的投影区间重叠，且在 y 轴上的投影区间也重叠。区间 [a1, a2] 和 [b1, b2] 的交集长度为正，当且仅当 min(a2, b2) > max(a1, b1)。
为什么正确
交集矩形的左边界是两个左边界的较大者，右边界是两个右边界的较小者；宽为正等价于右 > 左，y 方向同理。
复杂度分析
时间 O(1)，空间 O(1)。
易错点
比较必须用严格大于 >：用 >= 会把只共边或共角的情况误判为重叠。另外不要试图枚举“谁的角落在谁里面”，十字形交叉时没有任何角在对方内部。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
x_overlap = min(rec1[2], rec2[2]) > max(rec1[0], rec2[0])
y_overlap = min(rec1[3], rec2[3]) > max(rec1[1], rec2[1])
return x_overlap and y_overlapclass Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
boolean xOverlap = Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]);
boolean yOverlap = Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]);
return xOverlap && yOverlap;
}
}class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
bool xOverlap = min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]);
bool yOverlap = min(rec1[3], rec2[3]) > max(rec1[1], rec2[1]);
return xOverlap && yOverlap;
}
};func isRectangleOverlap(rec1 []int, rec2 []int) bool {
xOverlap := min(rec1[2], rec2[2]) > max(rec1[0], rec2[0])
yOverlap := min(rec1[3], rec2[3]) > max(rec1[1], rec2[1])
return xOverlap && yOverlap
}var isRectangleOverlap = function(rec1, rec2) {
const xOverlap = Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]);
const yOverlap = Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]);
return xOverlap && yOverlap;
};function isRectangleOverlap(rec1: number[], rec2: number[]): boolean {
const xOverlap = Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]);
const yOverlap = Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]);
return xOverlap && yOverlap;
}其他解法
投影法把二维问题拆成两个一维区间求交，边界自然正确；位置法从反面列举四种分离情况，直观但要额外注意退化矩形。
解法 2：反向判断不重叠的位置 时间 O(1)，空间 O(1)
两个正面积矩形不重叠，当且仅当一个完全在另一个的左边、右边、下边或上边（贴边也算不重叠）。先排除宽或高为 0 的退化矩形，再把这四种情况取或后取反。
从“什么时候肯定不重叠”反过来想，条件很直观。但必须单独处理面积为 0 的矩形，否则一条线段穿过另一个矩形时会误判为重叠；投影法用严格不等号自动处理了这种情况。
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
if rec1[0] == rec1[2] or rec1[1] == rec1[3] or rec2[0] == rec2[2] or rec2[1] == rec2[3]:
return False
return not (rec1[2] <= rec2[0] or rec2[2] <= rec1[0] or rec1[3] <= rec2[1] or rec2[3] <= rec1[1])class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
if (rec1[0] == rec1[2] || rec1[1] == rec1[3] || rec2[0] == rec2[2] || rec2[1] == rec2[3]) return false;
return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
}
}class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
if (rec1[0] == rec1[2] || rec1[1] == rec1[3] || rec2[0] == rec2[2] || rec2[1] == rec2[3]) return false;
return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
}
};func isRectangleOverlap(rec1 []int, rec2 []int) bool {
if rec1[0] == rec1[2] || rec1[1] == rec1[3] || rec2[0] == rec2[2] || rec2[1] == rec2[3] {
return false
}
return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1])
}var isRectangleOverlap = function(rec1, rec2) {
if (rec1[0] === rec1[2] || rec1[1] === rec1[3] || rec2[0] === rec2[2] || rec2[1] === rec2[3]) return false;
return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
};function isRectangleOverlap(rec1: number[], rec2: number[]): boolean {
if (rec1[0] === rec1[2] || rec1[1] === rec1[3] || rec2[0] === rec2[2] || rec2[1] === rec2[3]) return false;
return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
}