最大化网格图中正方形空洞的面积

标签: 数组 排序

难度: Medium

给你一个网格图，由 n + 2 条 横线段 和 m + 2 条 竖线段 组成，一开始所有区域均为 1 x 1 的单元格。

所有线段的编号从 1 开始。

给你两个整数 n 和 m 。

同时给你两个整数数组 hBars 和 vBars 。

  • hBars 包含区间 [2, n + 1] 内 互不相同 的横线段编号。
  • vBars 包含 [2, m + 1] 内 互不相同的 竖线段编号。

如果满足以下条件之一，你可以 移除 两个数组中的部分线段：

  • 如果移除的是横线段，它必须是 hBars 中的值。
  • 如果移除的是竖线段，它必须是 vBars 中的值。

请你返回移除一些线段后（可能不移除任何线段），剩余网格图中 最大正方形 空洞的面积，正方形空洞的意思是正方形 内部 不含有任何线段。

示例 1：

输入：n = 2, m = 1, hBars = [2,3], vBars = [2]
输出：4
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,3] 。
可以移除的横线段为 [2,3] ，竖线段为 [2] 。
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
操作后得到的网格图如右图所示。
正方形空洞面积为 4。
无法得到面积大于 4 的正方形空洞。
所以答案为 4 。

示例 2：

输入：n = 1, m = 1, hBars = [2], vBars = [2]
输出：4
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,3] ，竖线编号的范围是区间 [1,3] 。
可以移除的横线段为 [2] ，竖线段为 [2] 。
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
操作后得到的网格图如右图所示。
正方形空洞面积为 4。
无法得到面积大于 4 的正方形空洞。
所以答案为 4 。

示例 3：

输入：n = 2, m = 3, hBars = [2,3], vBars = [2,3,4]
输出：9
解释：左边的图是一开始的网格图。
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,5] 。
可以移除的横线段为 [2,3] ，竖线段为 [2,3,4] 。
一种得到最大正方形面积的方法是移除横线段 2、3 和竖线段 3、4 。
操作后得到的网格图如右图所示。
正方形空洞面积为 9。
无法得到面积大于 9 的正方形空洞。
所以答案为 9 。

提示：

  • 1 <= n <= 109
  • 1 <= m <= 109
  • 1 <= hBars.length <= 100
  • 2 <= hBars[i] <= n + 1
  • 1 <= vBars.length <= 100
  • 2 <= vBars[i] <= m + 1
  • hBars 中的值互不相同。
  • vBars 中的值互不相同。

Submission

运行时间: 24 ms

内存: 16.7 MB

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        def f(a : List) -> int:
            a.sort()
            n = len(a)
            mx = i = 0
            while i < n:
                st = i
                i += 1
                while i < n and a[i] - a[i - 1] == 1:
                    i += 1
                mx = max(mx, i - st)
            return mx + 1
        return min(f(hBars), f(vBars)) ** 2

Explain

为了找到最大的正方形空洞，首先我们需要确定在横向和纵向上可以形成的最大连续空洞的长度。这是因为正方形的大小由其最短的边决定。\n\n函数 `f(a)` 的作用是接收一个整数列表，这些整数代表可以移除的线段的编号。首先，将这些编号进行排序，然后遍历排序后的数组，寻找最长的连续序列，这个序列的长度即为在该方向上可以形成的最大空间的边长。\n\n遍历时，使用 `st` 记录当前连续序列的起始位置，`i` 用于探索序列的结束位置。如果当前位置和前一个位置的差值为1，则继续向前探索；否则，比较当前连续序列的长度和已知的最大长度，更新最大长度，并重置 `st`。\n\n最后，将最长连续序列的长度加1（因为长度n的序列对应的是n+1个连续的网格），然后在横向和纵向上找到的最长长度中取最小值，因为正方形的边长由短边决定。最后将这个长度的平方作为结果返回，因为面积是边长的平方。

时间复杂度: O(h log h + v log v)

空间复杂度: O(k)

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        def f(a: List[int]) -> int:
            a.sort()  # 对输入的线段编号进行排序
            n = len(a)
            mx = i = 0
            while i < n:
                st = i  # 记录连续序列的开始位置
                i += 1
                while i < n and a[i] - a[i - 1] == 1:
                    i += 1  # 探索连续序列的结尾
                mx = max(mx, i - st)  # 更新最长连续序列的长度
            return mx + 1  # 返回连续序列长度加1（网格数量）
        return min(f(hBars), f(vBars)) ** 2  # 计算最大正方形空洞的面积

Explore

在计算最大连续空洞时，需要将线段编号进行排序以确保能正确地计数连续的线段。如果不排序，线段编号可能是无序的，这样在遍历时无法直接通过比较相邻元素来判断是否连续。排序后，连续的线段编号将会相邻出现，这使得程序可以通过简单的递增遍历来找出最长的连续区间，从而确定最大的空洞边长。

如果输入的线段编号已经是连续的，函数`f(a)`的处理方式不变。首先，函数会检查列表是否已经排序，然后从列表的开始遍历，计算最长的连续区间。在这种情况下，整个列表本身就是一个连续区间，所以函数会在一次遍历中找到这个连续区间并计算其长度。最终返回的长度还需要加1，以反映连续线段所覆盖的网格数量。

在处理线段编号时，差值必须为1才认为是连续，是因为连续的线段编号表示这些线段在网格图中相邻。如果两个线段编号的差值为1，说明它们在网格中是挨着的，没有间断。如果差值大于1，这表示在两个编号之间至少有一个网格没有被覆盖，这导致连续性中断。在这种情况下，我们需要结束当前连续序列的计数，并在遇到下一个连续序列时重新开始计数。

函数`f(a)`返回连续序列的长度加1的处理方式背后的逻辑是，连续序列的长度实际上表示的是相邻线段之间的‘空档数’。例如，如果有一个连续序列的线段编号为[2, 3, 4]，那么这表示有三根线段，但实际上它们覆盖了四个网格（从网格2到网格5）。因此，我们需要在连续序列的长度基础上加1，以正确表示被这些连续线段覆盖的网格总数。