本文主要是介绍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 ) O(N^2) O(N2)的二重循环遍历任意两个矩形交叉部分当中可能的最大的正方形的面积。
然后,关于交叉部分的最大正方形的面积,这里又是一个分类讨论的问题,我们需要讨论以下两个矩形的分布情况,然后给出最终的答案。
2. 代码实现
给出python代码实现如下:
class Solution:def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:ans = 0n = len(bottomLeft)def get_intersection(rec1, rec2):if rec1[0] > rec2[0]:return get_intersection(rec2, rec1)if rec1[2] <= rec2[0]:return 0elif rec1[1] >= rec2[3] or rec1[3] <= rec2[1]:return 0l = 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 * dfor 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
提交代码评测得到:耗时4690ms,占用内存17.4MB。
这篇关于Leetcode 3047. Find the Largest Area of Square Inside Two Rectangles的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!