🧱 初学者友好指南 “最大化网格中正方形孔的面积” – LeetCode 2943 (C++, Python, JavaScript)

请提供您希望翻译的正文内容（除代码块和 URL 之外的文字），我会按照要求将其译成简体中文并保留原有的格式。

Problem Overview

给定：

• 两个整数 n 和 m，分别表示网格中内部水平条和垂直条的数量。
• 两个数组 hBars 和 vBars，列出可以被移除的具体条。

网格由条分隔成若干单元格。移除相邻的条会合并剩余固定条之间的空间。

• 移除一根条会产生 2 单位的间隙。
• 移除 k 根连续的条会产生 k + 1 单位的间隙。

你的目标是 找到通过移除任意数量可移除的条所能形成的正方形孔的最大面积。

关键洞察

问题可以拆分为两个相互独立的一维子问题：

1. 水平方向 – 找到最长的连续可移除水平杆序列。
2. 垂直方向 – 找到最长的连续可移除垂直杆序列。

如果最长的水平序列长度为 h，则最大水平间隙为 h + 1。
同理，长度为 v 的垂直序列产生的垂直间隙为 v + 1。

由于孔必须是 正方形，其边长受两者间隙中较小的限制：

side = min(maxHorizontalGap, maxVerticalGap)
area = side * side

算法

1. 排序 each array (hBars, vBars).
2. 扫描已排序的数组一次，以计算最长连续数字序列的长度。
3. 返回 longestRun + 1 作为该方向的最大间隙。
4. 将两侧间隙的最小值作为边长并将其平方。

伪代码

function getMaxGap(bars):
    sort(bars)
    maxRun = 1
    curRun = 1
    for i from 1 to bars.length-1:
        if bars[i] == bars[i-1] + 1:
            curRun += 1
        else:
            curRun = 1
        maxRun = max(maxRun, curRun)
    return maxRun + 1   // gap width

function maximizeSquareHoleArea(n, m, hBars, vBars):
    side = min(getMaxGap(hBars), getMaxGap(vBars))
    return side * side

复杂度分析

• 对每个数组进行排序：O(k log k)，其中 k 为数组的大小。
• 线性扫描：O(k)。

总体时间复杂度：O(n log n + m log m)。
空间复杂度：O(1) 额外（原地排序）。

参考实现

C++

class Solution {
public:
    int maximizeSquareHoleArea(int n, int m, std::vector<int>& hBars, std::vector<int>& vBars) {
        int side = std::min(getMaxGap(hBars), getMaxGap(vBars));
        return side * side;
    }

private:
    int getMaxGap(std::vector<int>& bars) {
        if (bars.empty()) return 1;          // no removable bars → gap of 1
        std::sort(bars.begin(), bars.end());

        int max_consecutive = 1;
        int current_consecutive = 1;

        for (size_t i = 1; i < bars.size(); ++i) {
            if (bars[i] == bars[i-1] + 1) {
                ++current_consecutive;
            } else {
                current_consecutive = 1;
            }
            max_consecutive = std::max(max_consecutive, current_consecutive);
        }
        return max_consecutive + 1;
    }
};

Python

def get_max_gap(bars: list[int]) -> int:
    if not bars:
        return 1
    bars.sort()
    max_consecutive = 1
    cur = 1
    for i in range(1, len(bars)):
        if bars[i] == bars[i - 1] + 1:
            cur += 1
        else:
            cur = 1
        max_consecutive = max(max_consecutive, cur)
    return max_consecutive + 1

def maximizeSquareHoleArea(n: int, m: int, hBars: list[int], vBars: list[int]) -> int:
    side = min(get_max_gap(hBars), get_max_gap(vBars))
    return side * side

JavaScript

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} hBars
 * @param {number[]} vBars
 * @return {number}
 */
var maximizeSquareHoleArea = function (n, m, hBars, vBars) {
    const getMaxGap = (bars) => {
        if (bars.length === 0) return 1;
        bars.sort((a, b) => a - b);
        let maxConsecutive = 1;
        let cur = 1;
        for (let i = 1; i < bars.length; i++) {
            if (bars[i] === bars[i - 1] + 1) {
                cur++;
            } else {
                cur = 1;
            }
            maxConsecutive = Math.max(maxConsecutive, cur);
        }
        return maxConsecutive + 1;
    };

    const side = Math.min(getMaxGap(hBars), getMaxGap(vBars));
    return side * side;
};

附加说明

• 为连续性进行排序：排序将问题简化为一次线性遍历，使整体时间复杂度为 O(k log k)。
• 栅栏效应考虑：k 根栅栏将 k + 1 个空间分隔开；移除它们会合并这些空间。
• 瓶颈原则：在任何方形约束中，较小的维度决定最终尺寸。

这种方法将二维网格问题转化为两个简单的一维扫描，常用于资源分配、窗口管理以及其他实际工程场景。