221-最大正方形

LeetCode 221. Maximal Square

LeetCode-221

Given an m x n binary matrix filled with 0‘s and 1‘s, find the largest square containing only 1’s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

method

dp[i][j]：以[i-1, j-1]结尾的子矩阵的最大正方形的边长

如果matrix[i-1][j-1]是1，就去看dp[i-1][j-1], dp[i-1][j], dp[i][j-1]的最小值，在最小值的基础上+1

int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int res = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                res = max(res, dp[i][j]);
            }
        }
    }
    return res * res;
}