首页 > 代码库 > Maximal Rectangle
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.
方法
使用两个矩阵,分别记录每一行连续的1的个数以及每一列连续的1的个数。public int maximalRectangle(char[][] matrix) { int lenX = matrix.length; if (lenX == 0) { return 0; } int lenY = matrix[0].length; int[][] maxRec = new int[lenX][lenY]; int[][] height = new int[lenX][lenY]; int[][] length = new int[lenX][lenY]; for (int i = 0; i < lenX; i++) { for (int j = 0; j < lenY; j++) { if (matrix[i][j] == '1') { if (j == 0) { length[i][j] = 1; } else { length[i][j] = length[i][j - 1] + 1; } if (i == 0) { height[i][j] = 1; } else { height[i][j] = height[i - 1][j] + 1; } } else { length[i][j] = 0; height[i][j] = 0; } } } for (int i = 0; i < lenX; i++) { for (int j = 0; j < lenY; j++) { int h = height[i][j]; int l = length[i][j]; int minHeight = h; int max = 0; for (int k = 1; k <= l; k++) { minHeight = Math.min(minHeight, height[i][j + 1 - k]); max = Math.max(max, k * minHeight); } maxRec[i][j] = max; } } int max = 0; for (int i = 0; i < lenX; i++) { for (int j = 0; j < lenY; j++) { if (maxRec[i][j] > max) { max = maxRec[i][j]; } } } return max; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。