lintcode：最大子正方形

题目：

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.

样例

For example, given the following matrix:

Return 4.

解题：

给定一个二维01矩阵，从中找出最大的全1正方形,并返回其面积。这里的面积就等于正方形中的1的个数。

说明：

1.给的01矩阵行列不一定相等。

2.最大正方形显然是有许多小的正方形组合起来了。

思路：

最小正方形就是这点的值是1，次小的正方形坐标是：

(i-1,j-1)	(i-1,j)
(i,j-1)	(i,j)

这里，考虑的是右下点是1的时候，再考虑其他三个点的情况，当其他三个点也都是1的时候，当前点(i,j)的值加一，表示形成的正方形边长是 A(i,j) + 1。

若上面的小正方形是另外一个大正方形的一部分，在判断大正方形的（i,j）点的时候，只需考虑其他三个点是否是零，非零表示可以构成正方形，同时选取这三个点所在值得最小值+ 1 做我该大正方形的边长。

Java程序：

public class Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
    public int maxSquare(int[][] matrix) {
        // write your code here
        if(matrix==null)
            return 0;
        int m = matrix.length;
        if(m ==0 )
            return 0;
        int n = matrix[0].length;
        if( n==0 )
            return 0;
        int res = -1;
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                if(matrix[i][j]!=0 ){
                    matrix[i][j] = min3(matrix[i-1][j-1],matrix[i][j-1],matrix[i-1][j]) + 1;
                }
                res = Math.max(res,matrix[i][j]);
                
            }
        }
        return res*res;
    }
    public int min3(int a ,int b,int c){
        a = Math.min(a,b);
        c = Math.min(a,c);
        return c;
    }
}

View Code

总耗时: 1978 ms

Python程序：

class Solution:
    #param matrix: a matrix of 0 and 1
    #return: an integer
    def maxSquare(self, matrix):
        # write your code here
        if matrix == None:
            return 0
        m = len(matrix)
        if m ==0:
            return 0
        n = len(matrix[0])
        if n ==0:
            return 0 
        dp = [[0]*n for _ in range(m)]
        ans = 0 
        for i in range(m):
            for j in range(n):
                dp[i][j] = matrix[i][j]
                if i and j and dp[i][j]:
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                ans = max(ans,dp[i][j])
        return ans*ans

View Code