原题
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例：
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"] ] 输出: 6
解法
思想
这道题可以分解成若干leetcode84-柱状图中最大的矩形的子问题，可以使用相同的方法。
我们从上往下动态规划二维数组，每增加一行就会出现不同的柱状区域。
从每一次得到的最大矩形面积中获取最大值，就是该题的答案
代码
class Solution {
public int largestRectangleArea(int[] heights) {
int length = heights.length;
if(length==0) return 0;
int max = 0;
int left[] = new int[length];
int right[] = new int[length];
left[0] = -1;
right[length-1] = length;
for(int i = 1;i<length;i++){
//如果左边一列比当前列矮，则left就等于左边一列的下标。
if(heights[i]>heights[i-1]) left[i] = i-1;
else{
//否则沿着左边这列的left一直查找过去，直到找到比当前列低的一列
left[i] = left[i-1];
while(left[i]!=-1&&heights[left[i]]>=heights[i])
left[i] = left[left[i]];
}
}
for(int i = length-2;i>=0;i--){
//如果右边一列比当前列矮，则right就等于右边一列的下标。
if(heights[i]>heights[i+1]) right[i] = i+1;
else{
//否则沿着右边这列的right一直查找过去，直到找到比当前列低的一列
right[i] = right[i+1];
while(right[i]!=length&&heights[right[i]]>=heights[i])
right[i] = right[right[i]];
}
}
for(int i = 0;i<length;i++){
int area = (right[i]-left[i]-1)*heights[i];
if(area>max) max = area;
}
return max;
}
public int maximalRectangle(char[][] matrix) {
if(matrix.length == 0) return 0;
int height[] = new int[matrix[0].length];
int max = 0;
for(char[] line:matrix){
//每增加一行改变height数组
for(int i=0;i<line.length;i++){
if(line[i]=='0') height[i]=0;
else height[i] += 1;
}
int area = largestRectangleArea(height);
if(area>max) max=area;
}
return max;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode85-%e6%9c%80%e5%a4%a7%e7%9f%a9%e5%bd%a2/
