网站建设数据库类型,鹤壁哪有做网站的,手机网站建设信息,微信网站可以免费做么Leetcode 2943. Maximize Area of Square Hole in Grid 1. 解题思路2. 代码实现 题目链接#xff1a;2943. Maximize Area of Square Hole in Grid
1. 解题思路
这一题的话其实横轴和竖轴可以分开来独立考察#xff0c;因为两者互不影响#xff0c;我们最终的答案一定是两…Leetcode 2943. Maximize Area of Square Hole in Grid 1. 解题思路2. 代码实现 题目链接2943. Maximize Area of Square Hole in Grid
1. 解题思路
这一题的话其实横轴和竖轴可以分开来独立考察因为两者互不影响我们最终的答案一定是两者之中能够构成的最大连续空格之中的较小值的平方。
因此我们只需要用贪婪算法分别考察横轴上和纵轴上能够获取的最大连续空洞即可。
2. 代码实现
给出python代码实现如下
class Solution:def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) - int:hBars sorted(hBars)vBars sorted(vBars)def get_max_block(bars):lb, nxt 1, 2ans 1for loc in bars:if loc nxt:nxt loc 1else:ans max(ans, nxt - lb)lb, nxt loc-1, loc1ans max(ans, nxt - lb)return ansh_max get_max_block(hBars)v_max get_max_block(vBars)ans min(h_max, v_max)return ans * ans提交代码评测得到耗时51ms占用内存16.4MB。
