Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

http://www.lintcode.com/en/problem/maximal-square/

Discussion

令状态dp[i][j]表示为从左上角(不一定是(0,0))到矩阵中坐标(i,j)为止能构成正方形的最大边长。那么有如下状态转移方程：

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1; if matrix[i][j] == 1
dp[i][j] = 0; if matrix[i][j] = 0

Solution

// Time:  O(m * n)
// Space: O(m * n)
class Solution {
public:
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    int maxSquare(vector<vector<int> > &matrix) {
        // write your code here
        int m = matrix.size();
        if(m==0) return 0;
        int n = matrix[0].size();
        if(n==0) return 0;
        int maxLen = 0;
        vector<vector<int> > len(m, vector<int> (n, 0));
        for(int i=0; i<m; i++) {//初始化
            len[i][0] = matrix[i][0]==1? 1: 0;
            maxLen = max(maxLen, len[i][0]);
        }
        for(int j=0; j<n; j++) {
            len[0][j] = matrix[0][j] == 1 ? 1 : 0;
            maxLen = max(maxLen, len[0][j]);
        }
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                if(matrix[i][j] == 1) {//状态转移
                    len[i][j] = min(len[i-1][j-1], min(len[i-1][j], len[i][j-1])) + 1;//三者之中最小的加1
                    maxLen = max(maxLen, len[i][j]);
                }
            }
        }
        return maxLen*maxLen;
    }
};

Solution 2

利用滚动数组降低空间复杂度

class Solution {
public:
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    int maxSquare(vector<vector<int> > &matrix) {
        // write your code here
        int m = matrix.size();
        if(m==0) return 0;
        int n = matrix[0].size();
        if(n==0) return 0;
        int maxLen = 0;
        vector<vector<int> > size(2, vector<int> (n, 0));
        /*for(int i=0; i<m; i++) {
            len[i][0] = matrix[i][0]==1? 1: 0;
            maxLen = max(maxLen, len[i][0]);
        }*/
        for(int j=0; j<n; j++) {
            size[0][j] = matrix[0][j];
            maxLen = max(maxLen, size[0][j]);
        }
        for(int i=1; i<m; i++) {
            size[i%2][0] = matrix[i][0];
            for(int j=1; j<n; j++) {
                if(matrix[i][j] == 1) {
                    size[i%2][j] = min(size[(i-1)%2][j-1], min(size[(i-1)%2][j], size[i%2][j-1])) + 1;
                    maxLen = max(maxLen, size[i%2][j]);
                } else {
                    size[i%2][j] = 0;
                }
            }
        }
        return maxLen*maxLen;
    }
};