Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int height[][] = new int[m][n+1];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(matrix[i][j]=='0') {
height[i][j] = 0;
} else if(i==0){
height[i][j] = 1;
} else {
height[i][j] = height[i-1][j] + 1;
}
}
}
int maxArea = 0;
for(int r=0;r<m;r++) {
int hei[] = height[r];
Stack<Integer> stk = new Stack<Integer>();
for(int i=0;i<hei.length;i++) {
int h = hei[i];
if(stk.isEmpty() || h>=hei[stk.peek()]) {
stk.push(i);
} else {
int tmp = stk.pop();
int area = hei[tmp] * (stk.isEmpty()?i:i-stk.peek()-1);
if(area>maxArea) {
maxArea = area;
}
i--;
}
}
}
return maxArea;
}
}
没有评论:
发表评论