[Leetcode] 221. Maximal Square | 最大正方形

yPhantom 2020年02月09日 27次浏览

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

求这个2D矩阵中能组成的最大面积。

记录这道题主要是为了记录经典的空间复杂度为O(mn)的转移方程:

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);

然后转成空间复杂度为O(2n):

int[] pre = new int[n];
int[] cur = new int[n];
cur[j] = min(cur[j - 1], pre[j], pre[j - 1])
swap(pre, cur)

时间复杂度最后是O(n)的:

int[] cur = new int[n];
int pre = 0;

for ():
  for ():
    temp = cur[j];
		cur = min(pre, cur[j], cur[j - 1]);
		pre = temp;

过程。

于这道题而言,求面积,我们可以得到边长的转移方程:

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

因此就有如下的代码了:

    class Solution {
        public int maximalSquare(char[][] matrix) {
            int m, n;
            if (matrix == null 
                || (m = matrix.length) == 0 
                || (n = matrix[0].length) == 0) {
                return 0;
            }
            int pre = 0;
            int[] cur = new int[n];
            int res = 0;
            for (int col = 0; col < n; col++) {
                if (matrix[0][col] == '1') {
                    cur[col] = 1;
                    res = Math.max(res, cur[col]);
                }
            }
            
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int temp = cur[j];
                    if (j == 0) {
                        cur[j] = matrix[i][j] - '0';
                    } else if (matrix[i][j] == '1'){
                        cur[j] = Math.min(pre, Math.min(cur[j], cur[j - 1])) + 1; 
                    } else {
                        cur[j] = 0;
                    }
                    res = Math.max(res, cur[j] * cur[j]);
                    pre = temp;
                }
            }
            return res;
        }
    }