Leetcode3047. 求交集区域内的最大正方形面积

Every day a Leetcode

题���来源：3047. 求交集区域内的最大正方形面积

解法1：枚举 + 几何

枚举两个矩形。

如果矩形有交集，那么交集一定是矩形。求出这个交集矩形的左下角和右上角。

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

  知道坐标就可以算出矩形的长和宽，取二者最小值作为正方形的边长。

  如果矩形没有交集，那么长和宽是负数，在计算面积前判断。

  代码：

  /* * @lc app=leetcode.cn id=3047 lang=cpp * * [3047] 求交集区域内的最大正方形面积 */// @lc code=startclass Solution{public:    long long largestSquareArea(vector &bottomLeft, vector &topRight)    {        int n = bottomLeft.size();        long long ans = 0LL;        for (int i = 0; i  0)                    ans = max(ans, (long long)size * size);            }        }        return ans;    }};// @lc code=end

  结果：

  复杂度分析：

  时间复杂度：O(n2)，其中 n 是数组 bottomLeft 的元素个数。

  空间复杂度：O(1)。