Leetcode 221.最大正方形

题目描述：

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

1
2

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

1
2

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

1
2

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 '0' 或 '1'

链接：

https://leetcode-cn.com/problems/maximal-square

题目分析

  我们首先思考一下，形成一个 n*n 的正方形的条件是什么？我们可以有这样的递归定义：四个角都可以形成 (n-1)*(n-1) 的正方形。那么我们就可以使用动态规划的方法了。我们使用 dp[i][j] 表示以 matrix[i][j] 为右下角的最大正方形边长，那么 dp[i][j] >= n 的充要条件是 dp[i-1][j]、dp[i][j-1] 和 dp[i-1][j-1] 都大于等于 n-1。而 dp[i][j] 的值，就取决于这三个数中最小的那个。当 matrix[i][j] 为 '0' 时，显然 dp[i][j] 为 0，也即其无法构成正方形。而当 matrix[i][j] 为 '1' 时，我们有这样的动态转移方程：

  而我们按顺序遍历矩阵，记录出现过的最大 dp 值（也即最大正方形边长）即可。需要注意的是当 i 或 j 为 0 时的边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        int maxsize = 0;
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = (i == 0 || j == 0) ? 1 : min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                    maxsize = max(maxsize, dp[i][j]);
                }
            }
        }
        return maxsize * maxsize;
    }
};

  时间复杂度：$O(mn)$，其中 $m、n$ 分别是矩阵的行数和列数。我们对矩阵进行了一次遍历。
  空间复杂度：$O(mn)$，其中 $m、n$ 分别是矩阵的行数和列数。我们需要和矩阵同样大小的 dp 数组。