给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
题解
1、暴力枚举
求每一个矩形
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) {
return 0;
}
//保存以当前数字结尾的连续 1 的个数
int[][] width = new int[matrix.length][matrix[0].length];
int maxArea = 0;
//遍历每一行
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
//更新 width
if (matrix[row][col] == '1') {
if (col == 0) {
width[row][col] = 1;
} else {
width[row][col] = width[row][col - 1] + 1;
}
} else {
width[row][col] = 0;
}
//记录所有行中最小的数
int minWidth = width[row][col];
//向上扩展行
for (int up_row = row; up_row >= 0; up_row--) {
int height = row - up_row + 1;
//找最小的数作为矩阵的宽
minWidth = Math.min(minWidth, width[up_row][col]);
//更新面积
maxArea = Math.max(maxArea, height * minWidth);
}
}
}
return maxArea;
}
// 作者：windliang
// 链接：https://leetcode-cn.com/problems/maximal-rectangle/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-1-8/
2、动态规划——使用柱状图的优化暴力方法
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int maxarea = 0;
// 动态规划
// dp[i][j]表示宽度i-j的宽度
int[][] dp = new int[matrix.length][matrix[0].length];
for (int i = 0;i < matrix.length; i++) {
for (int j = 0;j < matrix[0].length;j++) {
if (matrix[i][j] == '1'){
// 计算最大宽度，并更新
dp[i][j] = j == 0? 1 : dp[i][j-1]+1;
int width = dp[i][j];
// 计算最大的面积，在[i,j]较低的右下角
for (int k = i;k >= 0;k--) {
width = Math.min(width,dp[k][j]);
maxarea = Math.max(maxarea,width*(i-k+1));
}
}
}
}
return maxarea;
}
}
3、使用柱状图 - 栈
迭代求最大的面积
class Solution {
// 84题的解：利用栈从一个柱状图中获取最大的面积
public int leetcode84 (int [] heights) {
Stack<Integer> stack = new Stack<>();
stack.push(-1);
int maxarea = 0;
for (int i = 0;i < heights.length;i++) {
while(stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
maxarea = Math.max(maxarea,heights[stack.pop()]*(i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
maxarea = Math.max(maxarea,heights[stack.pop()]*(heights.length - stack.peek() - 1));
}
return maxarea;
}
// 85题的解答
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) {return 0;}
int maxarea = 0;
// dp 存储每一行的矩形值
int[] dp = new int[matrix[0].length];
// 遍历每一个位置
for (int i = 0;i < matrix.length;i++) {
for (int j = 0;j < matrix[0].length;j++) {
// 滚动数组，更新当前的柱状图
dp[j] = matrix[i][j] == '1' ? dp[i+1] : 0;
}
// 求当前柱状图的最大面结
maxarea = Math.max(maxarea,leetcode84(dp));
}
return maxarea;
}
}
4、动态规划——每个点的最大高度
public class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) { return 0; }
int m = matrix.length;// 行数
int n = matrix[0].length;// 列数
int[] left = new int[n];// 初始值为0
int[] right = new int[n];
int[] height = new int[n];// 初始值为 0
Arrays.fill(rigth,n);// 初始值为 n
int maxarea = 0;
// 对于每一列
for (int i = 0;i < m;i++) {
int cur_left = 0,cur_right = n;
// 更新高度
for (int j = 0;j < n;j++) {
if (martix[i][j] == '1') {
height[j]++;
} else {
height[j] = 0;
}
}
// 更新左侧
for (int j = 0;j < n;j++) {
if (matrix[i][j] == '1') {
// 更新历史最大值
left[j] = Math.max(cur_left,left[j]);
} else {
left[j] = 0;
cur_left = j+1;
}
}
// 更新右侧
for (int j = n - 1;j >= 0;j--) {
if (matrix[i][j] == '1') {
rigth[i] = Math.min(cur_right,rigth[i]);
} else {
right[j] = n;
cur_rigth = j;
}
}
// 迭代求最大的面结
for (int j = 0;j < n;j++) {
maxarea = Math.max(maxarea,(right[j]-left[j]) * height[j]);
}
}
return maxarea;
}
}
// 规范命名
class Solution {
public int maximalRectangle(char[][] matrix) {
int rows = matrix.length;
if (rows == 0) {
return 0;
}
int cols = matrix[0].length;
int[] height = new int[cols];
int[] left = new int[cols];
int[] right = new int[cols];
// 当前的左右边界值
int farthestLeft, farthestRight;
int maxArea = 0;
int currentArea;
Arrays.fill(right, cols);
for (int i = 0; i < rows; i++) {
farthestLeft = 0;
farthestRight = cols;
// 统计left边界
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == '1') {
left[j] = farthestLeft > left[j] ? farthestLeft : left[j];
}else {
left[j] = 0;
farthestLeft = j + 1;
}
}
// 统计height right 以及更新最大面积
for (int j = cols - 1; j >= 0; j--) {
if (matrix[i][j] == '1') {
height[j]++;
right[j] = farthestRight < right[j] ? farthestRight : right[j];
currentArea = (right[j] - left[j]) * height[j];
maxArea = currentArea > maxArea ? currentArea : maxArea;
}else {
height[j] = 0;
right[j] = cols;
farthestRight = j;
}
}
}
return maxArea;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
