首页 > 代码库 > Leetcode-Maximal Rectangle
Leetcode-Maximal Rectangle
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing all ones and return its area.
Analysis:
For each position (i,j), we calculate how many accumlative 1s at the left direction of this position at this row. We record this number at d[i][j]. For example, for matrix:
0 0 0 1 1 1
0 1 1 1 1 1
0 1 1 1 1 1
1 0 1 1 1 1
We have matrix d[i][j]
0 0 0 1 2 3
0 1 2 3 4 5
0 1 2 3 4 5
1 0 1 2 3 4
Then, at each postion (i,j), we scan the matrix along the upper direction and calculate the area of the maximum 1 matrix with the right bottom corner at (i,j). For row k<i, the 1s matrix should be (k-i+1)*min(d[l][j], l=k...i);
After caluclating the 1s matrix for each (i,j), we get the answer.
Solution:
1 public class Solution { 2 public int maximalRectangle(char[][] matrix) { 3 int rowNum = matrix.length; 4 if (rowNum==0) return 0; 5 int colNum = matrix[0].length; 6 if (colNum==0) return 0; 7 8 int[][] d = new int[rowNum][colNum]; 9 for (int i=0;i<rowNum;i++)10 for (int j=0;j<colNum;j++)11 if (j==0)12 if (matrix[i][j]==‘1‘) d[i][j]=1;13 else d[i][j]=0;14 else15 if (matrix[i][j]==‘1‘) d[i][j]=d[i][j-1]+1;16 else d[i][j]=0;17 18 int maxSoFar = -1;19 for (int i=0;i<rowNum;i++)20 for (int j=0;j<colNum;j++){21 int curMax = d[i][j];22 int minLen = d[i][j];23 for (int k=(i-1);k>=0;k--){24 if (d[k][j]==0) break;25 if (d[k][j]<minLen) minLen = d[k][j];26 int newMax = (i-k+1)*minLen;27 if (curMax<newMax) curMax = newMax;28 }29 if (curMax>maxSoFar) maxSoFar = curMax;30 31 }32 33 return maxSoFar;34 }35 }
Leetcode-Maximal Rectangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。