首页 > 其他 > 详细

leetcode--Maximal Rectangle

时间:2014-07-06 13:50:46      阅读:296      评论:0      收藏:0      [点我收藏+]

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). 

 

leetcode--Maximal Rectangle,布布扣,bubuko.com

leetcode--Maximal Rectangle

原文:http://www.cnblogs.com/averillzheng/p/3825713.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!