高效搜索二维数组中可放置指定尺寸对象的首个有效位置

问题回顾 #

给定元素为0/1的二维数组，需找到首个可完全容纳高h、宽w（均>1）的全0矩形区域的左上角坐标，区域需完全覆盖全0单元格。示例中3x3的目标区域返回{row: 2, col: 4}。核心优化方向为：

• 避免重复检查已验证区域
• 快速跳过无法容纳目标的区域

优化方案 #

1. 前缀和矩阵预处理：O(1)时间验证区域有效性 #

先构建前缀和矩阵，将任意矩形区域的求和操作从O(hw)降为O(1)，这是后续所有优化的基础。

构建方式：
定义prefix为(m+1)x(n+1)的矩阵（m为原数组行数，n为列数），其中prefix[i][j]表示原数组中从(0,0)到(i-1,j-1)的矩形区域元素总和。构建代码：

m, n = len(grid), len(grid[0])
prefix = [[0]*(n+1) for _ in range(m+1)]
for i in range(m):
    row_sum = 0
    for j in range(n):
        row_sum += grid[i][j]
        prefix[i+1][j+1] = prefix[i][j+1] + row_sum

区域验证：对于起始坐标(row, col)，目标区域为从(row, col)到(row+h-1, col+w-1)，计算其总和：

total = prefix[row+h][col+w] - prefix[row][col+w] - prefix[row+h][col] + prefix[row][col]
if total == 0:
    # 找到有效区域
    return {"row": row, "col": col}

2. 避免重复检查：标记无效起始点 #

当某个起始点被验证为无效（或因包含已知1必然无效），直接标记并跳过后续检查：

• 维护一个invalid二维布尔数组，初始全为False
• 若验证(row, col)无效，找到区域内任意一个1的位置(r, c)，则所有满足r - h +1 <= r' <= r且c -w +1 <= c' <= c的起始点(r', c')都会包含这个1，将这些(r', c')标记为invalid，后续遍历直接跳过

3. 跳过不可能区域：缩小遍历范围 #

• 提前限定有效遍历边界：起始行row的范围为0 <= row <= m - h，起始列col的范围为0 <= col <= n - w，超出该范围的位置直接跳过
• 预处理每行连续0区间：对每行预处理所有连续0的起始/结束索引，仅遍历那些连续0长度>=w的区间内的col位置——若某行从col开始的连续0长度不足w，该col不可能作为有效起始列，直接跳过

完整执行流程 #

1. 构建前缀和矩阵与每行连续0区间
2. 遍历所有有效范围内的(row, col)：
   • 若invalid[row][col]为True，跳过
   • 用前缀和验证目标区域是否全0，是则返回坐标
   • 若无效，标记所有受该区域内1影响的起始点为invalid
3. 若遍历完所有位置未找到，返回不存在有效区域

对比BFS/DFS的优势 #

BFS/DFS会遍历大量无关单元格，而本方案通过前缀和快速验证、无效点标记、范围预过滤，将时间复杂度从最坏O(mnhw)降至O(mn)（预处理）+ O(k)（k为有效候选起始点数量），大幅减少无效检查。

内容的提问来源于stack exchange，提问作者Hans Krohn