常德市网站建设_网站建设公司_外包开发_seo优化

题目信息

• 平台：LeetCode
• 题目：3047. 求交集区域内的最大正方形面积
• 难度：Medium
• 题目链接：Find the Largest Area of Square Inside Two Rectangles

题目描述

给定若干轴对齐矩形（用左下角与右上角坐标表示），任选两矩形，取它们的重叠区域。在所有重叠区域中，求能放下的最大正方形面积。

初步思路

1. 两矩形的交集仍是一个轴对齐矩形，其宽高可由区间交得出。
2. 交集矩形中最大正方形边长等于min(交集宽, 交集高)，面积为边长平方。
3. 枚举所有矩形对，更新最大面积即可。

算法分析

• 核心：枚举矩形对，计算交集宽高并取最小值作为正方形边长
• 技巧：交集宽高为min(tx1, tx2) - max(bx1, bx2)与min(ty1, ty2) - max(by1, by2)
• 正确性简述：任意两矩形的交集范围唯一，交集内能放下的最大正方形边长由更短边决定，枚举所有矩形对即可覆盖全局最优
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

代码实现（C++）

#include<bits/stdc++.h>usingnamespacestd;classSolution{public:longlonglargestSquareArea(vector<vector<int>>&bottomLeft,vector<vector<int>>&topRight){longlongmax_side=0;intn=(int)bottomLeft.size();for(inti=0;i<n;++i){for(intj=0;j<i;++j){intbx1=bottomLeft[i][0],by1=bottomLeft[i][1];inttx1=topRight[i][0],ty1=topRight[i][1];intbx2=bottomLeft[j][0],by2=bottomLeft[j][1];inttx2=topRight[j][0],ty2=topRight[j][1];intwidth=min(tx1,tx2)-max(bx1,bx2);intheight=min(ty1,ty2)-max(by1,by2);intside=min(width,height);if(side>0)max_side=max(max_side,(longlong)side);}}returnmax_side*max_side;}};

测试用例

总结与反思

1. 交集矩形的最大正方形边长由短边决定，先算交集再取最小值即可。
2. 枚举矩形对即可覆盖全局最优，注意side > 0才是有效交集。