# share my java solution beats 95.37% based on maxRectangleArea problem

• ``````public class Solution {

public int maximalRectangle(char[][] matrix) {
int m = matrix.length;
int n = m==0? 0:matrix[0].length;
int[][] heights = new int[m][n];
int maxArea = 0;
//initialize the historgram in every row
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(matrix[i][j] == '0'){
heights[i][j] = 0;
}else{
heights[i][j] = (i==0)? 1:heights[i-1][j]+1;
}
}
}
for(int i=0; i<m; i++){
maxArea = Math.max(maxArea,largestRectangleArea(heights[i]));
}
return maxArea;
}
public int largestRectangleArea(int[] heights){
if(heights==null || heights.length==0) return 0;
int[] left = new int[heights.length];
int[] right = new int[heights.length];
int result = 0;
left[0] = 0;
for(int i=1; i<heights.length; i++){
int currLeft = i-1;
while(currLeft>=0 && heights[currLeft]>=heights[i]){
currLeft = left[currLeft]-1;
}
left[i] = currLeft+1;
}
//build right
right[heights.length-1] = heights.length-1;
for(int i=heights.length-2; i>=0; i--){
int currRight = i+1;
while(currRight<heights.length && heights[i]<=heights[currRight]){
currRight = right[currRight]+1;
}
right[i] = currRight-1;
}
//compare right
for(int i=0; i<heights.length; i++){
result = Math.max(result, (right[i]-left[i]+1)*heights[i]);
}
return result;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.