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。

由于答案可能很大，返回结果模 10^9 + 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 <= 10^9
  • 1 <= hFences.length, vFences.length <= 600
  • 1 < hFences[i] < m
  • 1 < vFences[i] < n
  • hFences 和 vFences 是唯一的

解题思路

这道题要求在移除部分栅栏后形成最大的正方形。关键观察是：

  1. 边界分析：首先需要理解，字段本身有固定的边界栅栏（四周），这些不能移除。内部的栅栏可以选择性移除。

  2. 可能的边长：要形成正方形，我们需要找到水平和垂直方向上都能实现的边长。将边界坐标 1 和 m 加入 hFences，将 1 和 n 加入 vFences。任意两个水平栅栏之间的距离就是可能的水平边长，任意两个垂直栅栏之间的距离就是可能的垂直边长。

  3. 求交集：正方形的边长必须既是可能的水平边长，也是可能的垂直边长。因此需要找到两个边长集合的交集中的最大值。

  4. 优化策略：使用哈希集合存储所有可能的水平边长，然后遍历所有可能的垂直边长，在哈希集合中查找是否存在相同值，记录最大值。

具体实现：

  • 将边界坐标添加到栅栏数组
  • 计算所有可能的水平边长并存储到哈希集合
  • 计算所有可能的垂直边长，检查是否在水平边长集合中
  • 返回找到的最大公共边长的平方（面积）

代码实现

class Solution {
public:
    int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
        const int MOD = 1e9 + 7;
        
        // 添加边界
        hFences.push_back(1);
        hFences.push_back(m);
        vFences.push_back(1);
        vFences.push_back(n);
        
        // 计算所有可能的水平边长
        unordered_set<int> hLengths;
        int hSize = hFences.size();
        for (int i = 0; i < hSize; i++) {
            for (int j = i + 1; j < hSize; j++) {
                hLengths.insert(abs(hFences[i] - hFences[j]));
            }
        }
        
        // 计算所有可能的垂直边长，并找最大公共值
        int maxSide = 0;
        int vSize = vFences.size();
        for (int i = 0; i < vSize; i++) {
            for (int j = i + 1; j < vSize; j++) {
                int vLength = abs(vFences[i] - vFences[j]);
                if (hLengths.count(vLength)) {
                    maxSide = max(maxSide, vLength);
                }
            }
        }
        
        if (maxSide == 0) return -1;
        return (1LL * maxSide * maxSide) % MOD;
    }
};

class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        MOD = 10**9 + 7
        
        # 添加边界
        hFences.extend([1, m])
        vFences.extend([1, n])
        
        # 计算所有可能的水平边长
        h_lengths = set()
        for i in range(len(hFences)):
            for j in range(i + 1, len(hFences)):
                h_lengths.add(abs(hFences[i] - hFences[j]))
        
        # 计算所有可能的垂直边长，并找最大公共值
        max_side = 0
        for i in range(len(vFences)):
            for j in range(i + 1, len(vFences)):
                v_length = abs(vFences[i] - vFences[j])
                if v_length in h_lengths:
                    max_side = max(max_side, v_length)
        
        if max_side == 0:
            return -1
        return (max_side * max_side) % MOD

public class Solution {
    public int MaximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        const int MOD = 1000000007;
        
        // 添加边界
        var hList = new List<int>(hFences) { 1, m };
        var vList = new List<int>(vFences) { 1, n };
        
        // 计算所有可能的水平边长
        var hLengths = new HashSet<int>();
        for (int i = 0; i < hList.Count; i++) {
            for (int j = i + 1; j < hList.Count; j++) {
                hLengths.Add(Math.Abs(hList[i] - hList[j]));
            }
        }
        
        // 计算所有可能的垂直边长，并找最大公共值
        int maxSide = 0;
        for (int i = 0; i < vList.Count; i++) {
            for (int j = i + 1; j < vList.Count; j++) {
                int vLength = Math.Abs(vList[i] - vList[j]);
                if (hLengths.Contains(vLength)) {
                    maxSide = Math.Max(maxSide, vLength);
                }
            }
        }
        
        if (maxSide == 0) return -1;
        return (int)((1L * maxSide * maxSide) % MOD);
    }
}

var maximizeSquareArea = function(m, n, hFences, vFences) {
    const MOD = 1000000007;
    
    // Add boundary fences
    const hPositions = [1, ...hFences, m].sort((a, b) => a - b);
    const vPositions = [1, ...vFences, n].sort((a, b) => a - b);
    
    // Get all possible horizontal distances
    const hDistances = new Set();
    for (let i = 0; i < hPositions.length; i++) {
        for (let j = i + 1; j < hPositions.length; j++) {
            hDistances.add(hPositions[j] - hPositions[i]);
        }
    }
    
    // Get all possible vertical distances
    const vDistances = new Set();
    for (let i = 0; i < vPositions.length; i++) {
        for (let j = i + 1; j < vPositions.length; j++) {
            vDistances.add(vPositions[j] - vPositions[i]);
        }
    }
    
    // Find maximum common distance
    let maxSide = 0;
    for (const dist of hDistances) {
        if (vDistances.has(dist)) {
            maxSide = Math.max(maxSide, dist);
        }
    }
    
    return maxSide === 0 ? -1 : (BigInt(maxSide) * BigInt(maxSide) % BigInt(MOD));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(h² + v²)
空间复杂度O(h²)

其中 h 是水平栅栏数量（最多602个），v 是垂直栅栏数量（最多602个）。时间复杂度主要来自于计算所有可能的边长对，空间复杂度来自于存储水平边长的哈希集合。

相关题目