题目大意：
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=85
解题思路：
这道题开始并没有想到解法，不过后来发现，本题就是 LEETCODE 84. LARGEST RECTANGLE IN HISTOGRAM 的变形，我们从头来分析。
首先我们不可能一下子求出最大矩形面积，所以我们需要一行一行的来遍历，对于任意一行，都存在着一些0和1的数字，我们可以将数字为0的列的高度看做是0（即使0的上方存在1，但是在当前行，此列的高度就是0），而数字为1的列的高度要看1上方一共有多少个连续的1，他们的和就是当前列的高度。
计算列高度时，我们可以定义一个一维数组heights[]，数组的长度为题目给出的矩阵的宽。由第一行开始遍历，对于每一行，数字为1的列，对应heights下标的值加1，数字为0的列，对应heights的下标的值变为0即可。
这样，对于每一行，我们都可以得到一个高度数组，数组中的每个数可以看做是一个宽度为1，高度为数组对应下标值的一个矩形（矩形的高度可能为0），这样，问题就转化为在一组宽为1高度不同的矩形中找最大矩形面积的问题，这个问题和LEETCODE 84. LARGEST RECTANGLE IN HISTOGRAM 的描述是一模一样的。详细的方法可以参照84题的分析文章（这里强烈建议先做下84题）。为了阅读方便，这里再重复说下如何找到最大面积。
在一组连续排列的矩形中（我们可以将其理解为一些并排摆放的高度不等的柱子），他们组成的最大矩形面积是取决于最矮柱子的高度。因此我们遍历一遍高度，找到每棵柱子左右两边连续比自己高的柱子的范围，这样在该范围内，当前柱是最矮，所以当前柱的高度乘以范围的宽度，就是包含当前柱情况下能组成的最大矩形面积。同理当所有柱子都按照此法遍历完成之后，最大的矩形面积也就知道了。
看下完整代码：
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) {
return 0;
}
// 建立一个保存高度的数组
int[] heights = new int[matrix[0].length];
int max = 0;
// 循环矩阵的每一行
for (int i = 0; i < matrix.length; i++) {
// 循环当前行的每一列
for (int j = 0; j < matrix[0].length; j++) {
// 如果当前值为1，高度加一
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
// 如果当前值为0，高度清零
heights[j] = 0;
}
}
// 利用当前层得到的高度数组，求出其能组成的最大矩形面积
max = Math.max(max, largestRectangleArea(heights));
}
return max;
}
// 通过高度数组，求出其能组成的最大矩形面积
public int largestRectangleArea(int[] heights) {
if (heights.length == 0) {
return 0;
}
int[] leftBiggerCount = new int[heights.length];
for (int i = 0; i < heights.length; i++) {
if (heights[i] == 0) {
leftBiggerCount[i] = 1;
continue;
}
int count = 1;
int index = i - 1;
while (index >= 0 && heights[index] > heights[i]) {
count += leftBiggerCount[index];
index -= leftBiggerCount[index];
}
leftBiggerCount[i] = count;
}
int[] rightBiggerCount = new int[heights.length];
for (int i = heights.length - 1; i >= 0; i--) {
if (heights[i] == 0) {
rightBiggerCount[i] = 1;
continue;
}
int count = 1;
int index = i + 1;
while (index < heights.length && heights[index] >= heights[i]) {
count += rightBiggerCount[index];
index += rightBiggerCount[index];
}
rightBiggerCount[i] = count;
}
int max = 0;
for (int i = 0; i < heights.length; i++) {
max = Math.max(max, (rightBiggerCount[i] + leftBiggerCount[i] - 1) * heights[i]);
}
return max;
}本解法执行时间为4ms。
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-85-maximal-rectangle-解题思路分析/