移除栅栏得到的正方形田地的最大面积

标签: 数组 哈希表 枚举

难度: Medium

有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。

水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。

返回通过 移除 一些栅栏（可能不移除）所能形成的最大面积的 正方形 田地的面积，或者如果无法形成正方形田地则返回 -1。

由于答案可能很大，所以请返回结果对 109 + 7 取余 后的值。

注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏 不能 被移除。

示例 1：

输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。

示例 2：

输入：m = 6, n = 7, hFences = [2], vFences = [4]
输出：-1
解释：可以证明无法通过移除栅栏形成正方形田地。

提示：

  • 3 <= m, n <= 109
  • 1 <= hFences.length, vFences.length <= 600
  • 1 < hFences[i] < m
  • 1 < vFences[i] < n
  • hFences 和 vFences 中的元素是唯一的。

Submission

运行时间: 644 ms

内存: 36.2 MB

HYX_MOD_HYX = 1000000007


class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        hFences.append(1)
        vFences.append(1)
        hFences.append(m)
        vFences.append(n)
        hFences.sort()
        vFences.sort()

        # @functools.cache
        # def helper(l: int) -> bool:
        #     for i in range(len(vFences) - 1):
        #         j = len(vFences) - 1
        #         if vFences[j] - vFences[i] < l:
        #             return False
        #         left, right = i + 1, len(vFences)
        #         # while j > i and l < vFences[j] - vFences[i]:
        #         #     j -= 1
        #         while left < right:
        #             mid = (left + right) // 2
        #             tl = vFences[mid] - vFences[i]
        #             if tl > l:
        #                 right = mid
        #             elif tl == l:
        #                 return True
        #             else:
        #                 left = mid + 1
        # 
        #         if vFences[left] - vFences[i] == l:
        #             return True
        #     return False

        dic = set()
        for i in range(len(vFences) - 1):
            for j in range(i + 1, len(vFences)):
                dic.add(vFences[j] - vFences[i])

        max_len = min(m, n) - 1
        ans_l = -1
        for i in range(len(hFences) - 1):
            j = len(hFences) - 1
            if hFences[j] - hFences[i] <= ans_l:
                break
            while hFences[j] - hFences[i] > max_len:
                j -= 1
            while j > i:
                l = hFences[j] - hFences[i]
                if l <= ans_l:
                    break
                if l in dic:
                    ans_l = l
                else:
                    j -= 1
        return (ans_l * ans_l) % HYX_MOD_HYX if ans_l != -1 else -1

Explain

此题解的思路是首先对水平栅栏和垂直栅栏的坐标进行排序，并在两个数组的开始和结尾分别添加边界栅栏的坐标。然后，通过双重循环遍历所有可能的正方形的大小，对于每个大小，检查是否存在对应的水平栅栏和垂直栅栏组合来形成一个正方形。这是通过在一个集合中存储所有垂直栅栏间距的唯一值，并在遍历水平栅栏时检查该集合中是否存在与当前水平栅栏间距相等的值来实现的。如果找到这样的组合，则更新最大正方形的边长。最后，返回最大正方形的面积。

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

空间复杂度: O(h + v + v^2)

HYX_MOD_HYX = 1000000007


class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        hFences.append(1)
        vFences.append(1)
        hFences.append(m)
        vFences.append(n)
        hFences.sort()
        vFences.sort()

        dic = set()
        for i in range(len(vFences) - 1):
            for j in range(i + 1, len(vFences)):
                dic.add(vFences[j] - vFences[i])

        max_len = min(m, n) - 1
        ans_l = -1
        for i in range(len(hFences) - 1):
            j = len(hFences) - 1
            if hFences[j] - hFences[i] <= ans_l:
                break
            while hFences[j] - hFences[i] > max_len:
                j -= 1
            while j > i:
                l = hFences[j] - hFences[i]
                if l <= ans_l:
                    break
                if l in dic:
                    ans_l = l
                else:
                    j -= 1
        return (ans_l * ans_l) % HYX_MOD_HYX if ans_l != -1 else -1

Explore

集合（Set）被用来存储垂直栅栏的间距，因为集合具有唯一性和快速查找的特性。使用集合可以自动去除重复的间距值，并且在后续判断是否存在某个特定的间距时，集合能够提供平均常数时间复杂度的查找效率（O(1)时间复杂度）。若使用列表，查找一个元素的平均时间复杂度是O(n)，如果使用字典虽然也可以实现类似集合的效率，但其存储和管理键值对的额外结构在这里并不必要，因为我们只关心间距值的存在性，而不是它们的频率或其他属性。

在检查水平栅栏时从最大间距开始向内逐步减小间距进行检查的原因是，我们目标是找到最大的可能正方形边长。从最大可能间距开始并逐渐减小可以尽快地找到最大的合法边长。一旦发现一个合法的边长，由于边长是递减检查的，可以保证这是当前遍历过的最大合法边长，从而可以及时终止进一步的无效检查，提高算法的效率。

在题解中，一个有效的正方形是通过检查水平栅栏和垂直栅栏的间距是否相等来确认的。具体地，对于每一个考虑的水平栅栏间距，代码检查是否存在一个相同长度的垂直栅栏间距。如果这样的垂直间距存在于之前存储的集合中，那么说明可以构成一个边长为该间距的正方形。这时，如果这个边长比当前记录的最大边长还要大，就会更新最大边长的记录。

在计算结果时对`109 + 7`取余是常见的做法，尤其是在编程竞赛或算法实现中，主要是为了防止计算结果过大导致的整数溢出，并可以保持结果的稳定性。`1000000007`（10^9 + 7）是一个大质数，质数的使用在模运算中有良好的数学性质，可以减少潜在的哈希冲突，同时也是为了符合一些编程比赛的标准输出要求。