问题分析

本题是一道基于动态规划（DP） 的二维网格最大矩形面积问题，核心任务是在给定的网格中找到由空白格子（值为0）组成的最大矩形面积。网格中1表示障碍物，0表示可使用区域，最终需要计算最大可使用矩形的面积。

算法思路

1. 预处理辅助数组

为高效计算矩形的边界，预处理四个辅助数组：

• l[i][j]：第i行中，从位置j向左延伸的第一个障碍物的列坐标（即当前位置左侧最近障碍物的右边界）。
• r[i][j]：第i行中，从位置j向右延伸的第一个障碍物的列坐标（即当前位置右侧最近障碍物的左边界）。
• u[i][j]：第j列中，从位置i向上延伸的第一个障碍物的行坐标（即当前位置上方最近障碍物的下边界）。
• 这些数组的计算规则：
  • 若当前格子是障碍物（a[i][j] = 1），则l[i][j] = j，r[i][j] = j，u[i][j] = i。
  • 否则，l[i][j]继承左侧格子的l值，r[i][j]继承右侧格子的r值，u[i][j]继承上方格子的u值。

2. 优化边界计算

为确保矩形在垂直方向上的连续性，对每行的l和r数组进行优化：

• 若当前行的上方格子（i-1, j）是空白，则当前格子的l[i][j]取自身l值与上方格子l[i-1][j]的最大值（限制左边界不超过上方矩形的左边界）。
• 同理，r[i][j]取自身r值与上方格子r[i-1][j]的最小值（限制右边界不超过上方矩形的右边界）。

3. 动态规划求解最大面积

定义F(x, y)为以(x, y)为右下角的最大矩形面积，状态转移方程如下：

• 基础情况：F(x, y) = (x - u[x][y]) * (r[x][y] - l[x][y] - 1)，表示以当前格子为右下角，向上延伸至u[x][y]的矩形面积。
• 转移情况：
  • 若上方格子（x-1, y）是空白，则可与上方矩形合并：F(x-1, y) + (r[x][y] - l[x][y] - 1)。
  • 若左侧格子（x, l[x][y]）是空白，则可与左侧矩形合并：F(x, l[x][y]) + (r[x][y] - l[x][y] - 1) * (u[x][l[x][y]] - u[x][y])。
  • 若右侧格子（x, r[x][y]）是空白，则可与右侧矩形合并：F(x, r[x][y]) + (r[x][y] - l[x][y] - 1) * (u[x][r[x][y]] - u[x][y])。
• 最终结果为所有F(x, y)的最大值。

关键公式与复杂度

1. 辅助数组计算：

   • l[i][j] = a[i][j] ? j : l[i][j-1]（左边界）
   • r[i][j] = a[i][j] ? j : r[i][j+1]（右边界）
   • u[i][j] = a[i][j] ? i : u[i-1][j]（上边界） 时间复杂度：O(n^2)，其中n为网格边长。

2. DP状态转移： 每个状态F(x, y)的计算涉及常数次前驱状态查询，时间复杂度：O(n^2)。

3. 总时间复杂度：O(n^2)，空间复杂度：O(n^2)，适合处理n ≤ 2000的网格规模。

代码解析

算法的核心是通过预处理边界信息和动态规划，高效计算以每个空白格子为右下角的最大矩形面积，避免了暴力枚举的高复杂度，在二维网格问题中具有典型性和高效性。