寻找二维矩阵中最大正方形的面积

"最大正方形问题的算法解析与解答" 最大正方形问题是一个经典的计算机算法问题，主要出现在数据结构和算法的学习以及编程竞赛中。它要求在给定一个由'0'和'1'组成的二维矩阵中，找到仅包含'1'的最大正方形并返回其面积。这个问题涉及到动态规划（Dynamic Programming）的解决方法。 ### 题目描述 给定一个二维矩阵 `matrix`，其中每个元素是 '0' 或 '1'，任务是找出只包含 '1' 的最大正方形的面积。矩阵的大小范围是 1 到 300，且矩阵的行和列长度相等。例如： - 示例1： 输入：matrix=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4 解释：最大的正方形由 4 个 '1' 组成，如上图所示。 - 示例2： 输入：matrix=[["0","1"],["1","0"]] 输出：1 解释：只有一个 '1'，因此正方形面积为 1。 - 示例3： 输入：matrix=[["0"]] 输出：0 解释：没有 '1'，所以面积为 0。 ### 参考答案 ```cpp class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { if (matrix.size() == 0 || matrix[0].size() == 0) { return 0; } int maxSide = 0; int rows = matrix.size(), columns = matrix[0].size(); vector<vector<int>> dp(rows, vector<int>(columns)); // 初始化第一行和第一列 for (int i = 0; i < rows; i++) { dp[i][0] = (matrix[i][0] == '1') ? 1 : 0; } for (int j = 0; j < columns; j++) { dp[0][j] = (matrix[0][j] == '1') ? 1 : 0; } // 动态规划求解 for (int i = 1; i < rows; i++) { for (int j = 1; j < columns; j++) { if (matrix[i][j] == '1') { // 计算以当前元素为右下角的最大正方形边长 dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; maxSide = max(maxSide, dp[i][j]); } } } // 最大正方形面积为 maxSide * maxSide return maxSide * maxSide; } }; ``` 在上述代码中，我们创建了一个二维的辅助数组 `dp` 来存储到当前位置为止能形成的正方形的边长。初始化时，第一行和第一列的值分别等于对应位置的矩阵元素，因为它们只能形成宽度或高度为1的正方形。然后，对于矩阵中的每个元素，如果它是 '1'，则计算以该元素为右下角的正方形的边长，这个边长等于左边、上边和左上角相邻位置的最小值加1。同时更新最大边长 `maxSide`。最后，返回最大正方形的面积。 这个问题的关键在于动态规划的状态转移方程：`dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1`，这一步计算了以 `(i, j)` 为右下角的正方形的边长。通过这种自底向上、逐行推进的方式，我们可以有效地找出最大的正方形。 最大正方形问题通过动态规划可以高效地求解，避免了回溯和重复计算，具有较高的时间复杂度优化。