Leetcode 3047. Find the Largest Area of Square Inside Two Rectangles

• Leetcode 3047. Find the Largest Area of Square Inside Two Rectangles
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3047. Find the Largest Area of Square Inside Two Rectangles

1. 解题思路

这道题倒是没啥特别的思路，直接暴力求解就是了，因此就是一个$O(N^2)$的二重循环遍历任意两个矩形交叉部分当中可能的最大的正方形的面积。

然后，关于交叉部分的最大正方形的面积，这里又是一个分类讨论的问题，我们需要讨论以下两个矩形的分布情况，然后给出最终的答案。

2. 代码实现

给出python代码实现如下：

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        ans = 0
        n = len(bottomLeft)
        
        def get_intersection(rec1, rec2):
            if rec1[0] > rec2[0]:
                return get_intersection(rec2, rec1)
            if rec1[2] <= rec2[0]:
                return 0
            elif rec1[1] >= rec2[3] or rec1[3] <= rec2[1]:
                return 0
            l = min(rec2[2], rec1[2]) - rec2[0]
            if rec1[1] <= rec2[1]:
                h = min(rec1[3], rec2[3]) - rec2[1]
            else:
                h = min(rec1[3], rec2[3]) - rec1[1]
            d = min(h, l)
            return d * d
        
        for i in range(n):
            rec1 = [bottomLeft[i][0], bottomLeft[i][1], topRight[i][0], topRight[i][1]]
            for j in range(i+1, n):
                rec2 = [bottomLeft[j][0], bottomLeft[j][1], topRight[j][0], topRight[j][1]]
                ans = max(ans, get_intersection(rec1, rec2))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

提交代码评测得到：耗时4690ms，占用内存17.4MB。