首页 > 代码库 > 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.

 

public class Solution {    public int maximalRectangle(char[][] matrix) {        int row = matrix.length;		if(row == 0) return 0;				int column = matrix[0].length;		int[][] consecutiveOnes = new int[row][column];		for(int i = 0; i < row; ++i) {			for(int j = 0; j < column; ++j){				if(matrix[i][j] - ‘0‘ == 1){					if(j == 0) 						consecutiveOnes[i][j] = 1;					else 						consecutiveOnes[i][j] = consecutiveOnes[i][j - 1] + 1;				}				else					consecutiveOnes[i][j] = 0;			}		}				//calculate the max area. we check each element of consecutiveOnes column by column 		int maxArea = 0;		for(int i = 0; i < column; ++i){			for(int j = 0; j < row; ++j){				if(consecutiveOnes[j][i] != 0){					int minWidth = consecutiveOnes[j][i];					int index = j;					while(index >= 0 && consecutiveOnes[index][i] != 0){						minWidth = Math.min(minWidth, consecutiveOnes[index][i]);						maxArea = Math.max(maxArea, minWidth * (j - index + 1));						--index;					}				}			}		}		return maxArea;    }}

  

Remark: the second part (to seek the max area) can be solved by method used in "largest rectangle histogram" problem. Therefore, there is an algorithm with time O(row * column).