【Leetcode Daily】2943最大化网络图中正方形空洞的面积

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，给一个矩形，这个矩形已经被分割成了多个 1x1 正方形，又给了两个边集，现在只能从边集删边，求删边后矩形中能有的面积最大的正方形。

思路分享

• 正如灵神所说，这题最难的是读题。陆爻齐一开始理解成了只有边集的边才会成立，后面发现前面又说更开始都是 1x1 正方形矛盾而疑惑。但其实，边集和矩形中有多少边没关系，边集只限制了能删的边。所以求出两个方向中，最多连续可删的边的较小值平方就是本题答案。

  https://leetcode.cn/problems/maximize-area-of-square-hole-in-grid/solutions/2542812/heng-shu-fen-bie-tong-ji-fen-zu-xun-huan-nboj/?envType=daily-question&envId=2026-01-15

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    # 返回 a 排序后的最长连续递增子数组的长度
    def f(self, a: List[int]) -> int:
        a.sort()
        mx = cnt = 0
        for i, x in enumerate(a):
            if i > 0 and x == a[i - 1] + 1:
                cnt += 1
            else:
                cnt = 1  # 重新计数
            mx = max(mx, cnt)
        return mx

    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        side = min(self.f(hBars), self.f(vBars)) + 1
        return side * side