题目
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
思路
这个题可以看成上一题 84. 柱状图中最大的矩形（单调栈） 的拓展，我们一行一行的来分析这个矩阵：
第一行：[1, 0, 1, 0, 0]；第一至二行：[2, 0, 2, 1, 1]；第一至三行：[3, 1, 3, 2, 2]；、第一至四行：[4, 0, 0, 3, 0]；
显然拆成每行来看的话，就是求第一行到第 i 行组成的柱状图中的最大矩形，那么解法就很简单了；
代码
class Solution {
public int largestRectangleArea(int[] heights
) {
int ans
= 0;
Deque
<Integer> stack
= new ArrayDeque<>();
for (int i
=0; i
<heights
.length
; i
++){
while (!stack
.isEmpty() && heights
[i
] < heights
[stack
.peek()]){
int h
= heights
[stack
.pop()];
ans
= Math
.max(ans
, h
*(i
-stack
.peek()-1));
}
stack
.push(i
);
}
return ans
;
}
public int maximalRectangle(char[][] matrix
) {
if (matrix
.length
== 0)
return 0;
int ans
= 0;
int[] temp
= new int[matrix
[0].length
+2];
for (char[] chars
: matrix
) {
for (int j
=0; j
<chars
.length
; j
++) {
if (chars
[j
] != '0')
temp
[j
+1]++;
else
temp
[j
+1] = 0;
}
ans
= Math
.max(ans
, largestRectangleArea(temp
));
}
return ans
;
}
}
