0221. Maximal Square ==================== 题目信息 -------- :题号: 0221 :难度: Medium :主题: 矩阵、动态规划、正方形 :原题: `LeetCode 0221 `_ :重点: 连续方形区域、全部单元格为字符 1、返回面积而非边长 题目重述 -------- 给定一个 ``m x n`` 的字符矩阵 ``matrix``,每个单元格只可能是字符 ``'0'`` 或 ``'1'``。需要找出矩阵中面积最大的正方形,使该正方形覆盖的每个单元格都为 ``'1'``,并返回它的面积;题目不要求返回正方形的位置。 ``m`` 和 ``n`` 均位于 ``[1, 300]``。正方形必须由连续的行和连续的列组成;单独一个 ``'1'`` 也构成面积为 1 的正方形。若矩阵中没有 ``'1'``,返回 ``0``。输入矩阵无需修改。 自建示例 -------- 最大边长为 2: .. code-block:: text 输入:matrix = [["1","1","0","1"], ["1","1","1","1"], ["0","1","1","1"]] 输出:4 解释:右下区域存在多个边长为 2 的全 1 正方形,但不存在边长为 3 的全 1 正方形,因此最大面积为 2 x 2 = 4。 没有可用单元格: .. code-block:: text 输入:matrix = [["0","0"], ["0","0"]] 输出:0 解释:矩阵中没有字符 1,无法形成正面积的目标正方形。 以右下角定义状态 ---------------- 令 ``dp[j]`` 表示处理到当前行时,以当前列 ``j-1`` 为右边界、以当前行 为下边界的全 ``1`` 正方形最大边长。若当前单元格是 ``'0'``,任何以它为右下角的 目标都不存在,所以状态为 0。若当前单元格是 ``'1'``,它能扩成的最大边长取决于三个相邻状态: * 上方状态:限制正方形的上方区域; * 左方状态:限制左侧区域; * 左上方状态:限制内部已经形成的较小正方形。 因此有: .. math:: dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 这里的 ``dp[i][j]`` 表示以矩阵单元格 ``(i,j)`` 为右下角的边长,不是面积;扫描过程中记录最大边长, 最后平方得到面积。 滚动数组实现 ~~~~~~~~~~~~ 用一维数组保存上一行。更新当前列前,``dp[j]`` 还是上方状态;``dp[j-1]`` 已经更新为左方状态; 另存的 ``previous_diagonal`` 是左上方状态。计算完成后再把旧的 ``dp[j]`` 保存为下一列的左上方状态, 更新顺序不能颠倒。 正确性说明 ---------- 若一个全 ``1`` 正方形以 ``(i,j)`` 为右下角且边长大于 1,那么去掉最后一行、最后一列以及右下角后, 它要求上方、左方和左上方分别存在至少边长减一的正方形。因此边长不能超过三个邻居状态的最小值, 加上当前的 ``'1'`` 后得到的最小值加一正好可行。对所有单元格取最大边长,就覆盖了每个可能的右下角, 其平方即为全矩阵最大正方形面积。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int maximalSquare(std::vector>& matrix) { if (matrix.empty() || matrix[0].empty()) return 0; const int rows = static_cast(matrix.size()); const int columns = static_cast(matrix[0].size()); std::vector dp(columns + 1, 0); int best = 0; for (int row = 0; row < rows; ++row) { int previous_diagonal = 0; for (int column = 1; column <= columns; ++column) { const int upper = dp[column]; if (matrix[row][column - 1] == '1') { dp[column] = 1 + std::min({ dp[column], dp[column - 1], previous_diagonal }); best = std::max(best, dp[column]); } else { dp[column] = 0; } previous_diagonal = upper; } } return best * best; } }; 代码分析 -------- ``upper`` 必须在覆盖 ``dp[column]`` 前保存,否则左上方状态会被破坏。遇到 ``'0'`` 时显式清零, 避免把上一行的正方形错误延伸到当前行。每个单元格只处理一次,时间复杂度为 ``O(mn)``,滚动数组额外 占 ``O(n)`` 空间,返回的面积不需要另建矩阵。