首页 > 代码库 > 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).
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。