【每日一题】最小面积矩形——从平行坐标轴到任意角度的完整攻略

一、题目对比题目LeetCode 939LeetCode 963题目名称最小面积矩形最小面积矩形 II边的限制必须平行于 x 轴和 y 轴任意角度不一定平行于坐标轴数据范围1 ≤ points.length ≤ 5001 ≤ points.length ≤ 50返回值整数面积浮点数面积误差 1e-5 内难度中等中等二、LeetCode 939最小面积矩形边平行于坐标轴2.1 题目描述给定在 xy 平面上的一组点确定由这些点组成的矩形的最小面积其中矩形的边平行于 x 轴和 y 轴。如果没有任何矩形返回 0。示例输入[[1,1],[1,3],[3,1],[3,3],[2,2]] 输出42.2 解题思路核心观察对于边平行于坐标轴的矩形只需要确定一条对角线即可确定整个矩形。如果已知矩形的两个对角点(x1, y1)和(x2, y2)那么另外两个点必然是(x1, y2)和(x2, y1)。算法流程将所有点存入哈希集合set实现 O(1) 查找枚举每一对点作为对角线检查另外两个角是否存在于点集中计算面积并更新最小值2.3 Python 代码实现classSolution:defminAreaRect(self,points:List[List[int]])-int: 思路枚举对角线 哈希集合查找 时间复杂度O(N^2)空间复杂度O(N) # 将所有点存入集合便于 O(1) 查找point_setset(map(tuple,points))nlen(points)resfloat(inf)# 枚举每一对点作为对角线foriinrange(n):x1,y1points[i]forjinrange(i1,n):x2,y2points[j]# 如果两点在同一水平线或垂直线上无法形成矩形ifx1x2ory1y2:continue# 检查另外两个顶点是否存在if(x1,y2)inpoint_setand(x2,y1)inpoint_set:# 计算矩形面积areaabs(x1-x2)*abs(y1-y2)resmin(res,area)return0ifresfloat(inf)elseres2.4 优化版本按列分组另一种思路是按 x 坐标分组然后找两列之间的公共 y 坐标fromcollectionsimportdefaultdictclassSolution:defminAreaRect(self,points:List[List[int]])-int: 优化思路按列分组找公共纵坐标 时间复杂度O(N^2) ~ O(N^1.5) 实际运行很快 columnsdefaultdict(list)forx,yinpoints:columns[x].append(y)# 记录 (y1, y2) - 最右侧出现的 x 坐标seen{}resfloat(inf)forxinsorted(columns):columncolumns[x]column.sort()mlen(column)# 枚举当前列中所有的纵坐标对foriinrange(m):forjinrange(i1,m):y1,y2column[i],column[j]# 如果之前见过这对纵坐标可以形成矩形if(y1,y2)inseen:widthx-seen[(y1,y2)]heighty2-y1 resmin(res,width*height)# 更新这对纵坐标最后出现的位置seen[(y1,y2)]xreturn0ifresfloat(inf)elseres三、LeetCode 963最小面积矩形 II边不平行于坐标轴3.1 题目描述给定 X-Y 平面上的点数组points返回由这些点形成的任意矩形的最小面积矩形的边不一定平行于 X 轴和 Y 轴。如果不存在矩形返回 0。示例输入points [[1,2],[2,1],[1,0],[0,1]] 输出2.00000 解释最小面积矩形由 [1,2]、[2,1]、[1,0]、[0,1] 组成面积为 2。3.2 解题思路核心观察矩形的两条对角线互相平分且长度相等即对角线中点相同且半长相等。算法流程枚举中心法枚举所有点对计算其中点坐标和半长到端点的距离按照中点坐标 半长作为 key 进行分组同一组内的任意两条线段可以构成一个矩形计算矩形面积取最小值为什么这样能确定矩形两条线段有相同中点 → 互相平分两条线段半长相等 → 对角线长度相等对角线互相平分且相等的四边形 → 矩形3.3 Python 代码实现importmathfromcollectionsimportdefaultdictfromtypingimportListclassSolution:defminAreaFreeRect(self,points:List[List[int]])-float: 思路枚举中心法 - 矩形的对角线互相平分中点相同且长度相等 - 按 (中点x, 中点y, 半长平方) 分组 时间复杂度O(N^2)空间复杂度O(N^2) nlen(points)# key: (中点x, 中点y, 半长平方) - value: 该组内的所有点groupsdefaultdict(list)# 枚举所有点对foriinrange(n):x1,y1points[i]forjinrange(i1,n):x2,y2points[j]# 计算中点坐标用 2*mid 避免浮点数精度问题mid_xx1x2 mid_yy1y2# 计算半长平方避免开方减少精度误差half_len_sq(x1-x2)**2(y1-y2)**2# 存入分组groups[(mid_x,mid_y,half_len_sq)].append((i,j))resfloat(inf)# 遍历每个分组组内任意两条线段可形成矩形forkey,pairsingroups.items():mlen(pairs)ifm2:continue# 枚举组内所有线段对foriinrange(m):p1_idx,p2_idxpairs[i]x1,y1points[p1_idx]forjinrange(i1,m):p3_idx,p4_idxpairs[j]x3,y3points[p3_idx]# 计算矩形面积 |向量1| * |向量2| * sin(夹角)# 等价于以两条对角线的一半为邻边的平行四边形面积的 2 倍# 或者利用叉积计算# 向量 p1-p3 和 p1-p4 是矩形的两条邻边# 但更简单的方法利用对角线性质# 面积 |AC| * |BD| * sin(theta) / 2# 其中 theta 是对角线夹角# 实际计算用向量叉积# 取 p1, p2 为一条对角线p3, p4 为另一条# 矩形的四个顶点为 p1, p3, p2, p4或类似排列# 计算向量vx1,vy1x3-x1,y3-y1# p1 - p3vx2,vy2x4-x1,y4-y1# p1 - p4 (x4, y4 需要先定义)# 修正我们需要正确获取 p4 的坐标# 实际上同一组内的两条线段 (p1,p2) 和 (p3,p4)# 矩形的四个顶点是 p1, p3, p2, p4# 计算邻边向量# 从 p1 出发到 p3 和 p4 的两条边x4,y4points[p4_idx]# 向量 p1-p3a1,b1x3-x1,y3-y1# 向量 p1-p4a2,b2x4-x1,y4-y1# 矩形面积 |a1*b2 - a2*b1| 叉积的绝对值areaabs(a1*b2-a2*b1)resmin(res,area)return0.0ifresfloat(inf)elsefloat(res)3.4 更简洁的实现推荐importmathfromcollectionsimportdefaultdictfromtypingimportListclassSolution:defminAreaFreeRect(self,points:List[List[int]])-float: 优化实现更清晰的面积计算 nlen(points)point_setset(map(tuple,points))resfloat(inf)# 枚举三个点确定第四个点foriinrange(n):x1,y1points[i]forjinrange(i1,n):x2,y2points[j]forkinrange(j1,n):x3,y3points[k]# 假设 (x2,y2) 和 (x3,y3) 是对角点# 第四个点 p2 p3 - p1 (向量运算)x4x2x3-x1 y4y2y3-y1# 检查第四个点是否存在if(x4,y4)notinpoint_set:continue# 检查是否是矩形邻边垂直点积为0# 向量 p1-p2 和 p1-p3dx1,dy1x2-x1,y2-y1 dx2,dy2x3-x1,y3-y1# 点积为0说明垂直ifdx1*dx2dy1*dy20:# 计算面积 |p1p2| * |p1p3|areamath.sqrt(dx1**2dy1**2)*math.sqrt(dx2**2dy2**2)resmin(res,area)return0.0ifresfloat(inf)elseres四、两道题目的对比总结对比维度LeetCode 939LeetCode 963核心性质边平行坐标轴 → 只需对角线两点任意角度 → 对角线互相平分且等长关键判定检查(x1,y2)和(x2,y1)是否存在检查第四个点是否存在 邻边垂直数据结构set存储所有点set存储所有点 分组或三重点枚举时间复杂度O(N²)O(N³) 或 O(N²)空间复杂度O(N)O(N) 或 O(N²)精度问题无整数运算需注意浮点数精度用叉积避免开方五、关键技巧与注意事项5.1 哈希集合的使用两道题都利用了哈希集合set实现 O(1) 的点查找这是解决几何问题的常用技巧。5.2 避免浮点数精度问题在 LeetCode 963 中中点计算使用2 * mid存储避免浮点数距离计算比较距离平方而非距离避免开方面积计算使用叉积公式|a×b| |x1*y2 - x2*y1|避免三角函数5.3 复杂度权衡939 题数据范围大500 点必须用 O(N²) 算法963 题数据范围小50 点O(N³) 枚举三重点完全可接受六、参考题目LeetCode 939枚举对角线 哈希集合LeetCode 963枚举中心法 / 枚举三角形法LeetCode 223矩形面积基础几何LeetCode 836矩形重叠区间重叠判定总结从平行于坐标轴的矩形到任意角度的矩形核心思路都是从对角线性质出发。939 题利用坐标轴平行的特性简化问题963 题则需要利用对角线互相平分且等长的矩形判定定理。掌握这两种思路可以应对大部分矩形相关的几何问题。