Leetcode3047. 求交集区域内的最大正方形面积
Every day a Leetcode
题目来源:3047. 求交集区域内的最大正方形面积
解法1:枚举 + 几何
枚举两个矩形。
如果矩形有交集,那么交集一定是矩形。求出这个交集矩形的左下角和右上角。
- 左下角横坐标:两个矩形左下角横坐标的最大值。
- 左下角纵坐标:两个矩形左下角纵坐标的最大值。
- 右上角横坐标:两个矩形右上角横坐标的最小值。
- 右上角纵坐标:两个矩形右上角纵坐标的最小值。
知道坐标就可以算出矩形的长和宽,取二者最小值作为正方形的边长。
如果矩形没有交集,那么长和宽是负数,在计算面积前判断。
代码:
/*
* @lc app=leetcode.cn id=3047 lang=cpp
*
* [3047] 求交集区域内的最大正方形面积
*/
// @lc code=start
class Solution
{
public:
long long largestSquareArea(vector<vector<int>> &bottomLeft, vector<vector<int>> &topRight)
{
int n = bottomLeft.size();
long long ans = 0LL;
for (int i = 0; i < n - 1; i++)
{
auto &b1 = bottomLeft[i];
auto &t1 = topRight[i];
for (int j = i + 1; j < n; j++)
{
auto &b2 = bottomLeft[j];
auto &t2 = topRight[j];
int w = min(t1[0], t2[0]) - max(b1[0], b2[0]);
int h = min(t1[1], t2[1]) - max(b1[1], b2[1]);
int size = min(w, h);
if (size > 0)
ans = max(ans, (long long)size * size);
}
}
return ans;
}
};
// @lc code=end
结果:
复杂度分析:
时间复杂度:O(n2),其中 n 是数组 bottomLeft 的元素个数。
空间复杂度:O(1)。
原文地址:https://blog.csdn.net/ProgramNovice/article/details/136323563
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!