leetcode 3047

3047: 求交集区域内的最大正方形面积

bottomLeft[i]和topRight[i]分别代表第i个矩形的左下角和右上角坐标。

如果两个矩形有交集，那么交集也是矩形。

求出这个交集矩形的左下角和右上角，就可以算出交集矩形的长和宽。

• 左下角横坐标：两个矩形左下角横坐标的最大值。
• 左下角纵坐标：两个矩形左下角纵坐标的最大值。
• 右上角横坐标：两个矩形右上角横坐标的最小值。
• 右上角纵坐标：两个矩形右上角纵坐标的最小值。

长和宽的最小值，就是能放入交集区域的正方形的最大边长 side。

最大的 side 的平方（正方形面积）即为答案。

优化：外层循环枚举的矩形，如果其长或宽 ≤maxSide，那么交集矩形的长或宽也 ≤maxSide，所以 maxSide 不会变大，无需跑内层循环，直接 continue。

class Solution { public: long long largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) { int max_side=0; for(int i=0;i<bottomLeft.size();i++){ auto& b1=bottomLeft[i]; //取别名 auto& t1=topRight[i]; if(t1[0]-b1[0]<=max_side || t1[1]-b1[1]<=max_side) continue; for(int j=0;j<i;j++){ auto& b2=bottomLeft[j]; auto& t2=topRight[j]; int width=min(t1[0],t2[0])-max(b1[0],b2[0]); //右上横坐标-左下横坐标 int height=min(t1[1],t2[1])-max(b1[1],b2[1]); //右上纵坐标-左下纵坐标 int side=min(width,height); max_side=max(max_side,side); } } return (long long)max_side*max_side; } };