问题

0,1矩阵中最大的全1正方形

例如:

int[][] a = {
    {0, 1, 1, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {1, 1, 0, 1, 1},
    {1, 1, 1, 1, 1},
    {0, 1, 1, 1, 0},
    {0, 1, 1, 1, 0},
};

答案应该是: 2

解答

朴素的思路

思路上是把一个二维搜索问题变成了一个一维搜索问题
即将二维数组转化为柱状图, 在柱状图上找正方形, 例如上述例子转为柱状图后:

0, 1, 1, 1, 0, 
0, 2, 0, 2, 0, 
0, 3, 1, 3, 0, 
1, 4, 2, 4, 1, 
2, 5, 0, 5, 2, 
3, 6, 1, 6, 3, 
0, 7, 2, 7, 0, 
0, 8, 3, 8, 0, 

具体的找法比较绕口, 不如直接看代码:

private static int findMaxSquare(int[][] array){
    if(array.length == 0) return 0;

    int rows = array.length, cols = array[0].length;
    for(int i = 1; i < rows; i++){
        for(int j = 0; j < cols; j++){
            if(array[i][j] > 0){
                array[i][j] = array[i - 1][j] + 1;
            }
        }
    }

    int maxVal = 0;
    for(int[] row : array){
        for(int i = 0; i < cols - maxVal; i++){
            if(row[i] > maxVal){
                int cnt = 0, maxLen = row[i];
                for(int j = i; j < cols && cnt < maxLen && row[j] > cnt; j++, cnt++){
                    maxLen = Math.min(maxLen, row[j]);
                }
                maxVal = Math.max(maxVal, cnt);
            }
        }
    }
    return maxVal;
}

简单的来说, 就是找到可能的正方形左下角点以后, 向右搜索(cnt < maxLen && row[j] > cnt):

• 一方面走的步数(cnt)不能大于目前已经走过的所有值的最小值(maxLen)
• 另外一方面已经走过的值(row[j])必须大于当前走过的步数(cnt)

总而言之, 这是一个最坏情况O(N^3)的方法, 不过总体来说, 其实性能不算太差.

动态规划

如果一个点的它的左边, 左上, 上边至少构成某个长度(n)的正方形的话, 那么这个点应该能构成一个更大的正方形(n+1)
这样说起来可能有点绕...看例子吧:

0, 1, 1, 1, 0, 
0, 1, 0, 1, 0, 
0, 1, 1, 1, 0, 
1, 1, 2, 2, 1, 
1, 2, 0, 1, 2, 
1, 2, 1, 1, 2, 
0, 1, 2, 2, 0, 
0, 1, 2, 3, 0, 

题目中的例子整个状态空间如上图所示, 很显然...状态方程如下是成立的:

$$dp[i][j] = \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1$$

所以实现下来的话...

private static int findMaxSquare(int[][] array){
    if(array.length == 0) return 0;
    int rows = array.length, cols = array[0].length, maxVal = 0;
    
    int[][] dp = new int[rows][cols];
    for(int i = 0; i < rows; i++){
        if(array[i][0] == 1){
            dp[i][0] = 1;
            maxVal = 1;
        }
    }
    for(int j = 0; j < cols; j++){
        if(array[0][j] == 1){
            dp[0][j] = 1;
            maxVal = 1;
        }
    }

    for(int i = 1; i < rows; i++){
        for(int j = 1; j < cols; j++){
            if(array[i][j] == 1){
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
            maxVal = Math.max(maxVal, dp[i][j]);
        }
    }
    return maxVal;
}

总而言之, 这是一个最坏情况O(N^2)的方法, 只用把数组扫描一遍即可Orz

总结

动态规划的主要难点在于想出状态方程...