LeetCode-221-Maximal-Square

Posted on In

题目描述

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

1
2
3
4
5
6
7
8
Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

解析

题目给了一堆0和1组成的矩阵，问矩阵中由1组成的方块的最大面积

这是我本人非常喜欢的一道题目，描述得十分简洁，实现算法从暴力到DP，能够体现出计算机科学以及算法的优雅，暴力的方法非常显而易见，穷尽所有的可能性，一行一行，发现连续的1则往下继续探索，看看是否满足方阵的要求，即长宽相等，Leetcode官方题解给出的代码如下，而且居然能够AC，可见样例比较弱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int maxsqlen = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    int sqlen = 1;
                    boolean flag = true;
                    while (sqlen + i < rows && sqlen + j < cols && flag) {
                        for (int k = j; k <= sqlen + j; k++) {
                            if (matrix[i + sqlen][k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        for (int k = i; k <= sqlen + i; k++) {
                            if (matrix[k][j + sqlen] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag)
                            sqlen++;
                    }
                    if (maxsqlen < sqlen) {
                        maxsqlen = sqlen;
                    }
                }
            }
        }
        return maxsqlen * maxsqlen;
    }
}

不过这题还有一个更为巧妙的方法，利用dp，我们用dp[i][j]来表示以(i, j)为右下角的方阵的边长，如图：

递推公式如下：

根据递推公式，就能够用少量代码十分优雅地解决这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maximalSquare(char[][] matrix) {
        if(matrix.length == 0)
            return 0;
        int res = 0;
        int[][] dp = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(matrix[i][j] == '1'){
                    int left = i - 1 > -1 ? dp[i - 1][j] : 0;
                    int up = j - 1 > - 1 ? dp[i][j - 1] : 0;
                    int dig = i - 1 > - 1 && j - 1 > -1 ? dp[i - 1][j - 1] : 0;
                    dp[i][j] = 1 + Math.min(left, Math.min(up,dig));
                    // 注意这里dp存的是边长，结果要返回面积
                    res = Math.max(res, dp[i][j] * dp[i][j]);
                }
            }
        }
        return res;
    }

时间复杂度为$O(mn)$，空间复杂度为$O(mn)$，其中m、n为矩阵长宽

Follow Up

如果要找一个最大矩形的面积呢？