Maximal Square

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

Example:

Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

解法一：
比较直观的解法就是使用动态规划，建立一个二维结果数组result[n][n]。那么result[i][j] = max( result[i][j-1], result[i-1][j]) + 1 或者 +0. 有了这个转移关系，我们注意到只有在右下角出现一个1的时候才可能有正方形，所以在出现1的时候做一个检查。代码如下：

class Solution {
public:
    //s[m,n], s[m, n+1], s[m+1, n], s[m+1, n+1]
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(0 == m) {
            return 0;
        }
        
        int n = matrix[0].size();
        vector<vector<char>> result(m, vector<char>(n, 0)); 
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(matrix[i][j] == '0') {
                    if(i == 0 && j > 0) {
                        result[i][j] = result[i][j-1];
                    }
                    else if(j==0 && i > 0) {
                        result[i][j] = result[i-1][j];
                    }
                    else if(i==0 && j ==0) {
                        result[i][j] = 0;
                    }
                    else {
                        result[i][j] = max(result[i-1][j], result[i][j-1]);   
                    }
                }
                else {
                    if(i==0  ||  j==0) {
                        result[i][j] = 1;
                    }  
                    else {
                        int temp = max(result[i-1][j], result[i][j-1]) + 1;
                        if(check(temp, matrix, i, j)) {
                            result[i][j] = temp;
                        }
                        else {
                            result[i][j] = temp - 1;
                        }   
                    }
                }
            }
        }
        
        return result[m-1][n-1]*result[m-1][n-1];
    }
    
    bool check(int n, vector<vector<char>>& matrix, int x, int y) {
        if(x < n-1 || y < n-1) {
            return false;
        }
        
        bool flag = true;
        for(int i = x; i > x-n; i--) {
            for(int j=y; j > y-n; j--) {
                if(matrix[i][j] == '0') {
                    flag = false;
                    break;
                }
            }
            
            if(!flag) {
                break;
            }
        }
        
        return flag;
    }
};

上面的解法无疑是一种简单的正向思维，并且有点啰嗦。当矩阵全是1的时候每次都检查，效率比较低。考虑到当找到右下角一个1的时候，有递推式result[i][j] = min(result[i-1][j-1], result[i-1][j], result[i][j-1]) + 1。然后记录当前已知的最大正方形边长maxl = max(maxl, result[i][j]). 从而返回的结果为maxl*maxl。这个结果相对而言更好的利用了动态规划的子结果。代码如下：

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

从运行效率上看，第二种方式比第一种方式好很多。