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

 

[解题思路]

1.brute force

枚举所有sub-matrix(O(N^2), N = m*n) ，检查每个子矩阵是不是都是1，如果是更新最大面积，检查子矩阵是否都是1需要

花费O(N). 故总的时间为O(N^3) N = m*n

可以过小数据，大数据直接TLE

1 public int maximalRectangle(char[][] matrix) { 2         // Start typing your Java solution below 3         // DO NOT write main() function 4         int m = matrix.length; 5         if(m == 0){ 6             return m; 7         } 8         int n = matrix[0].length; 9         if(n == 0){10             return n;11         }12         13         return generateMaxArea(matrix);14     }15     16     private static int generateMaxArea(char[][] matrix) {17         int m = matrix.length;18         int n = matrix[0].length;19         int maxArea = 0;20         for (int i = 1; i <= m; i++) {21             for (int j = 1; j <= n; j++) {22                 int subMatrixArea = enumerateSubMatrix(matrix, i, j);23                 if (subMatrixArea > maxArea) {24                     maxArea = subMatrixArea;25                 }26             }27         }28         return maxArea;29     }30 31     public static int enumerateSubMatrix(char[][] matrix, int i, int j) {32         int m = matrix.length;33         int n = matrix[0].length;34         int subMatrixArea = 0;35         for (int p = 0; p <= (m - i); p++) {36             for (int q = 0; q <= (n - j); q++) {37                 int area = getSubMatrixArea(matrix, p, q, p + i - 1, q + j - 1);38                 if (area > subMatrixArea) {39                     subMatrixArea = area;40                 }41             }42         }43         return subMatrixArea;44     }45 46     private static int getSubMatrixArea(char[][] matrix, int p, int q, int i,47             int j) {48         for (int m = p; m <= i; m++) {49             for (int n = q; n <= j; n++) {50                 if (matrix[m][n] == '0') {51                     return 0;52                 }53             }54         }55 56         return (i - p + 1) * (j - q + 1);57     }

 2.DP

令dp[i][j]表示点(i,j)开始向右连续1的个数，花费O(M*N)的时间可以计算出来

接着从每个点开始，将该点作为矩形左上角点，从该点开始向下扫描直到最后一行或者dp[k][j] == 0

每次计算一个矩形的面积，与最大面积进行比较，如最大面积小于当前面积则进行更新，总的时间复杂度为O(M*N*M)

1 public int maximalRectangle(char[][] matrix) { 2         // Start typing your Java solution below 3         // DO NOT write main() function 4         int m = matrix.length; 5         if(m == 0){ 6             return m; 7         } 8         int n = matrix[0].length; 9         int[][] dp = new int[m][n];10         11         for(int i = 0; i < m; i++){12             for(int j = 0; j < n; j++){13                 if(matrix[i][j] == '0'){14                     continue;15                 } else {16                     dp[i][j] = 1;17                     int k = j + 1;18                     while(k < n && (matrix[i][k] == '1')){19                         dp[i][j] += 1;20                         k++;21                     }22                 }23             }24         }25         int maxArea = 0;26         for(int i = 0; i < m; i++){27             for(int j = 0; j < n; j++){28                 if(dp[i][j] == 0){29                     continue;30                 } else{31                     int area = 0, minDpCol = dp[i][j];32                     for(int k = i; k < m && dp[k][j] > 0; k++){33                         if(dp[k][j] < minDpCol){34                             minDpCol = dp[k][j];35                         }36                         area = (k - i + 1) * minDpCol;37                         if(area > maxArea){38                             maxArea = area;39                         }40                     }41                 }42             }43         }44         return maxArea;45     }