题目信息
LeetoCode地址: 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目理解
该题是84题的升级版。84题给出了一个一维数组，即一行数据，每个元素是高度。而该题则是给出了二维数组，只需我们将每一行的高度自行求出，即可以运用相同的算法解决。
该题目的难点在于思维模型上，如何借助单调栈和数组给出的信息进行快速求解。
以示例1为例：
如果将每一行的1的高度(即连续的1的长度)以黄色标注出来，会发现只包含1的最大矩形出现在第三行里，2*3=6.
不难发现，每一个矩形都是由一列一列1组成的，我们要找到的就是能够组成最大矩形的那些列！
要找到它，我们需要总结一些规律
- 矩形的长度和高度越大越好
- 矩形的每一列高度一定相等
是的，只需要关注上面两条规律就足够了！我们在遍历每一行元素时，如果遇到某一列比之前的列小，那它就一定和之前比它高的列（同一行之前的列）没有任何关系了！此时需要回过头来算账，计算之前那些更高的列能够组成的最大矩阵有多大？高度我们已经确定，唯一需要确定的就是长度，即维持该高度的左右下标。显然，我们应该使用一种数据结构存储这样的下标，由于我们要倒着拿下标数据，栈就是最合适的了。那什么时候存下标呢？由于我们遇到更短的列时才会倒着拿数据，那当然要在当前列不短于上一列的情况下去插入下标了！！
口说无凭，让我们根据第三行的列高度数据来推演一下吧！
heightArray[2] = {3,1,3,2,2}
stack = {}
最初时栈是空的，此时是没有数据给你复盘的，所以我们要把3的下标存入栈
stack = {0}
然后我们看第二个元素1，糟糕，它比第一列还要短，它帮不上前面的列的忙了，所以我们要往回看，直到栈空，或者展栈内元素都不小于1.
由于栈里只有3，所以我们分析高度不小于3的列的左右下标。左下标显然是-1，因为不存在其他元素了。又下标则是当前元素1的下标1. 然后我们就可以更新一下可能的最大矩形面积=(右下标-左下标-1) * 高度 = (1-(-1) -1)* 3 = 3.
与第一列有关系的最大矩形求完了，它的下标也没有继续呆在栈里的意义了，所以我们出栈，继续上一过程，直到栈空，或者展栈内元素都不小于1.
很显然，3出栈完后这一过程就结束了，我们可以将第一列的1下标入栈，继而遍历低3列下标2的高度。又是3！而且比第二列大，它能帮的上忙！所以我们将它入栈。
stack = {1,2}
继续看第4列，嗯，它比栈顶元素高度3小，所以我们要重复上面出栈的过程。
可能的最大矩形面积= (3-1-1)*3 = 3.
栈顶2出栈后，新栈顶的高度和当前列的高度一样的，所以我们不再出栈，继续放入该列下标
stack={1,3}
继续看第5列，它和栈顶元素高度一样大，入栈！
stack={1,3,4}
至此，该行的所有元素都遍历完了，但是我们的工作并没有结束。因为栈还没有空。很显然，现在栈里每一个元素的高度，都可以维持到该行的最后一个元素！
所以我们要一个一个出栈，计算它们到该行最右边列所可能组成的最大矩形面积
对于下标4，可能的最大矩形面积= (5-3-1)*2 = 2.
对于下标3，可能的最大矩形面积= (5-1-1)*2 = 6.
对于下标1，可能的最大矩形面积= (5-(-1)-1)*1 = 5.
该行结束。其余的每一行都是按照该方法进行遍历，最后可以很容易得到最终答案6.
单调栈 写法
在实现上有一个小技巧，我们不用真的使用Deque，Stack等封装类，仅仅使用一个数组+指针的方式即可模拟栈，在时间效率上会更高。
public int maximalRectangle(char[][] matrix) {
int max = 0;
int h = matrix.length;
int l = matrix[0].length;
int[] heights = new int[l];
for (int i = 0; i< h;i++) {
//该循环可以累计每行的高度
for (int j = 0; j < l; j++) {
if (matrix[i][j] == '0') {
heights[j] = 0;
} else {
heights[j]++;
}
}
max = Math.max(max, findMax(heights));
}
return max;
}
private int findMax(int[] heights) {
int l = heights.length;
//使用数组模拟栈
int[] stack = new int[l];
// 栈顶指针, 值为-1时代表该栈为空
int stackTopIdx = -1;
int i = 0;
int max = 0;
while (i < l) {
//栈空时入栈
if (stackTopIdx == -1) {
stack[++stackTopIdx] = i++;
} else {
//当前列高度大于等于栈顶，入栈
if (heights[i] >= heights[stack[stackTopIdx]]) {
stack[++stackTopIdx] = i++;
} else {
//当前列高度小于栈顶列，出栈结算直到栈空或者栈顶列高度小于等于当前列
//注意，该分支内i的值是没有++的，会循环遍历直到满足上述条件
int height = heights[stack[stackTopIdx--]];
// 此处如果发现栈里仅存在唯一一个元素，则说明之前不存在其他元素，亦或者是所有其他元素所对应的高度均超过height，所以我们可以大胆假设leftIndex = -1
int leftIndex = stackTopIdx <= -1 ? -1 : stack[stackTopIdx];
int rightIndex = i;
max = Math.max(max, (rightIndex-leftIndex-1) * height);
}
}
}
//该行所有列都遍历完栈还不为空，说明最后若干列高度越来越大
//我们需要手动出列计算它们能够组成的最大矩形
while (stackTopIdx>=0) {
int height = heights[stack[stackTopIdx--]];
int leftIndex = stackTopIdx <= -1 ? -1 : stack[stackTopIdx];
max = Math.max(max, (l-leftIndex-1) * height);
}
return max;
}在Matrix 高m, 长n的规模下
时间复杂度: O(m*n),最复杂的操作是遍历每行列高度,以及在每一行里找寻最大矩阵文章来源：https://www.toymoban.com/news/detail-830610.html
额外空间复杂度: O(n),我们需要一个临时数组存储每行的列高度，以及栈。文章来源地址https://www.toymoban.com/news/detail-830610.html
到了这里，关于Leetcode 85. 最大矩形的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
