Medium

题目描述

给你两个整数 n 和 m，以及两个整数数组 hBars 和 vBars。网格有 n + 2 条水平条和 m + 2 条垂直条，形成 1 x 1 的单位格子。条的索引从 1 开始。

你可以从水平条中移除 hBars 中的一些条，从垂直条中移除 vBars 中的一些条。注意其他条是固定的，不能移除。

在移除一些条（可能不移除）后，返回网格中正方形洞的最大面积。

示例 1：

输入: n = 2, m = 1, hBars = [2,3], vBars = [2]
输出: 4
解释: 左图显示了由条形成的初始网格。水平条是 [1,2,3,4]，垂直条是 [1,2,3]。
获得最大正方形洞的一种方法是移除水平条 2 和垂直条 2。

示例 2：

输入: n = 1, m = 1, hBars = [2], vBars = [2]
输出: 4
解释: 为了获得最大的正方形洞，我们移除水平条 2 和垂直条 2。

示例 3：

输入: n = 2, m = 3, hBars = [2,3], vBars = [2,4]
输出: 4
解释: 获得最大正方形洞的一种方法是移除水平条 3 和垂直条 4。

约束条件：

  • 1 <= n <= 10^9
  • 1 <= m <= 10^9
  • 1 <= hBars.length <= 100
  • 2 <= hBars[i] <= n + 1
  • 1 <= vBars.length <= 100
  • 2 <= vBars[i] <= m + 1
  • hBars 中所有值都不相同
  • vBars 中所有值都不相同

解题思路

这道题的核心思想是：要形成一个正方形洞，我们需要在水平和垂直方向上都有连续的可移除条。

分析思路：

  1. 理解条的编号：网格有 n+2 条水平条（编号 1 到 n+2）和 m+2 条垂直条（编号 1 到 m+2）。边界条（编号 1 和 n+2/m+2）不能移除。

  2. 寻找连续序列：对于 hBars 和 vBars，我们需要找到最长的连续整数序列。如果我们能移除连续的 k 条水平条，就能在水平方向创造 k+1 个单位的空间。

  3. 计算最大正方形：正方形的边长受限于水平和垂直方向的最小值。如果水平方向最多能创造 h 个单位的空间，垂直方向最多能创造 v 个单位的空间，那么正方形的边长就是 min(h, v)。

  4. 算法步骤：

    • 对 hBars 和 vBars 分别排序
    • 找到每个数组中最长的连续整数序列长度
    • 连续序列长度 + 1 就是该方向上能创造的最大空间
    • 取两个方向的最小值作为正方形边长
    • 返回边长的平方

时间复杂度：主要是排序的 O(k log k)，其中 k 是数组长度（最多 100）。

代码实现

class Solution {
public:
    int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {
        auto getMaxConsecutive = [](vector<int>& bars) -> int {
            sort(bars.begin(), bars.end());
            int maxLen = 1, currentLen = 1;
            
            for (int i = 1; i < bars.size(); i++) {
                if (bars[i] == bars[i-1] + 1) {
                    currentLen++;
                } else {
                    maxLen = max(maxLen, currentLen);
                    currentLen = 1;
                }
            }
            maxLen = max(maxLen, currentLen);
            return maxLen + 1; // +1 because removing k bars creates k+1 units of space
        };
        
        int maxH = getMaxConsecutive(hBars);
        int maxV = getMaxConsecutive(vBars);
        
        int sideLength = min(maxH, maxV);
        return sideLength * sideLength;
    }
};

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        def getMaxConsecutive(bars):
            bars.sort()
            max_len = 1
            current_len = 1
            
            for i in range(1, len(bars)):
                if bars[i] == bars[i-1] + 1:
                    current_len += 1
                else:
                    max_len = max(max_len, current_len)
                    current_len = 1
            
            max_len = max(max_len, current_len)
            return max_len + 1  # +1 because removing k bars creates k+1 units of space
        
        max_h = getMaxConsecutive(hBars)
        max_v = getMaxConsecutive(vBars)
        
        side_length = min(max_h, max_v)
        return side_length * side_length

public class Solution {
    public int MaximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        int GetMaxConsecutive(int[] bars) {
            Array.Sort(bars);
            int maxLen = 1, currentLen = 1;
            
            for (int i = 1; i < bars.Length; i++) {
                if (bars[i] == bars[i-1] + 1) {
                    currentLen++;
                } else {
                    maxLen = Math.Max(maxLen, currentLen);
                    currentLen = 1;
                }
            }
            maxLen = Math.Max(maxLen, currentLen);
            return maxLen + 1; // +1 because removing k bars creates k+1 units of space
        }
        
        int maxH = GetMaxConsecutive(hBars);
        int maxV = GetMaxConsecutive(vBars);
        
        int sideLength = Math.Min(maxH, maxV);
        return sideLength * sideLength;
    }
}

var maximizeSquareHoleArea = function(n, m, hBars, vBars) {
    function getMaxConsecutive(bars) {
        bars.sort((a, b) => a - b);
        let maxLen = 1;
        let currentLen = 1;
        
        for (let i = 1; i < bars.length; i++) {
            if (bars[i] === bars[i-1] + 1) {
                currentLen++;
            } else {
                maxLen = Math.max(maxLen, currentLen);
                currentLen = 1;
            }
        }
        maxLen = Math.max(maxLen, currentLen);
        return maxLen;
    }
    
    const maxH = getMaxConsecutive(hBars);
    const maxV = getMaxConsecutive(vBars);
    const side = Math.min(maxH, maxV) + 1;
    
    return side * side;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(k log k)
空间复杂度O(1)

其中 k 是 hBars 和 vBars 数组的长度（最大为 100）。时间复杂度主要来自排序操作，空间复杂度为常数级别（原地排序）。

相关题目