Maximal Rectangle (Java)

LeetCode

Maximal Rectangle

 Total Accepted: 2599 Total Submissions: 12591

Given a 2D binary matrix filled with 0's and 1's,

 find the largest rectangle containing all ones and 

return its area.

Similar question with largest rectangle in histogram but 

more tough.

we can apply a helper table to convert matrix to another

int[][] helper with calculate the current height for 1 at each 

column until current row.

Such as

char[][] matrix       -> int[][] helper

0,0,0,1,0                   0,0,0,1,0

0,1,1,0,1                   0,1,1,0,1

0,1,1,1,0                   0,2,2,1,0

0,0,1,0,1                   0,0,3, 0,1

then we can apply the method used in largest rectangle in

histogram to get max area which used current row as bottom

then keep updating max area.

	/*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 MaximalRectangle {
	public int maximalRectangle(char[][] matrix) {
	if (matrix==null ||matrix.length==0){
	return 0;
	}
	int[][] heights=new int[matrix.length][matrix[0].length];
	// build heights table, once we have heights table, at each row, we can use
	// method which used in question of Largest Rectangle in Histogram to calculate
	// max area at until this row,.
	for (int row=0; row<matrix.length; row++){
	for (int col=0; col<matrix[0].length; col++){
	if (row==0){
	heights[row][col]=matrix[row][col]=='0'?0:1;
	}
	else{
	heights[row][col]=matrix[row][col]=='0'?0:heights[row-1][col]+1;
	}
	}
	}
	int max=0;
	for (int row=0; row<heights.length; row++){
	// update max with maxArea of each row
	max=Math.max(max, maxArea(heights[row]));
	}
	return max;
	}
	// calculate maxArea for each row
	private int maxArea(int[] heights){
	if (heights==null||heights.length==0){
	return 0;
	}
	Stack<Integer> stack=new Stack<Integer>();
	int max=0;
	int i=0;
	while(i<heights.length){
	if (stack.isEmpty()||heights[stack.peek()]<=heights[i]){
	stack.push(i);
	i++;
	}
	else{
	int height=heights[stack.pop()];
	int width=stack.isEmpty()?i:i-stack.peek()-1;
	max=Math.max(max, height*width);
	}
	}
	while(!stack.isEmpty()){
	int height=heights[stack.pop()];
	int width=stack.isEmpty()?i:i-stack.peek()-1;
	max=Math.max(max, height*width);
	}
	return max;
	}
	}

view raw MaximalRectangle.java hosted with ❤ by GitHub