Maximal Square

221. 最大正方形

分析

初始化：
- n 和 m 分别为矩阵的行数和列数。
- 状态表示：f[i][j] 表示以 matrix[i-1][j-1] 为右下角的最大正方形的边长
状态转移：
- 对于每一个 matrix[i - 1][j - 1] == '1'，我们通过状态转移方程更新 f[i][j] 的值
- f[i][j] 的值是通过左边、上边和左上角的最小值加 1 来计算的，表示我们可以扩展一个更大的正方形：f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1
更新最大边长：
- 每次更新 f[i][j] 时，比较当前 f[i][j] 的值是否大于当前最大边长 res，如果大于，则更新 res
返回结果：
- 最终返回的结果是 res * res，即最大正方形的面积

时间复杂度

时间复杂度 O(n * m)

空间复杂度

空间复杂度为 O(n * m)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution
{
public:
    int maximalSquare(vector<vector<char>>& matrix)
    {
        // 判断输入矩阵是否为空
        if (matrix.empty() || matrix[0].empty())
            return 0;

        int n = matrix.size(), m = matrix[0].size();

        // 初始化状态表示 f，大小为 (n+1) * (m+1)
        std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1));
        int res = 0;  // 存储最大正方形的边长

        // 遍历矩阵每个元素
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (matrix[i - 1][j - 1] == '1')  // 如果当前位置是 '1'
                {
                    // 更新 f[i][j] 为左边、上边和左上角最小值加 1
                    f[i][j] = std::min(f[i - 1][j], std::min(f[i][j - 1], f[i - 1][j - 1])) + 1;
                    // 更新最大正方形边长
                    res = std::max(res, f[i][j]);
                }

        // 返回最大正方形的面积
        return res * res;
    }
};