题目描述（困难难度）

给一个只有 0 和 1 的矩阵，输出一个最大的矩形的面积，这个矩形里边只含有 1。

解法一 暴力破解

参考-solution-for-your-reference>)，遍历每个点，求以这个点为矩阵右下角的所有矩阵面积。如下图的两个例子，橙色是当前遍历的点，然后虚线框圈出的矩阵是其中一个矩阵。

怎么找出这样的矩阵呢？如下图，如果我们知道了以这个点结尾的连续 1 的个数的话，问题就变得简单了。

1. 然后向上扩展一行，高度增加一，选出当前列最小的数字，作为矩阵的宽，如上图，当前列中有 和 4 ，那么，就将 作为矩形的宽，求出面积，对应上图的矩形圈出的部分。

2. 然后继续向上扩展，重复步骤 2。

按照上边的方法，遍历所有的点，以当前点为矩阵的右下角，求出所有的矩阵就可以了。下图是某一个点的过程。

以橙色的点为右下角，高度为 1。

高度为 2。

高度为 3。

代码的话，把求每个点累计的连续 1 的个数用 保存，同时把求最大矩形的面积和求 width融合到同一个循环中。

时间复杂度：O（m²n）。

解法二

参考这里-solution-based-on-Largest-Rectangle-in-Histogram>)，接下来的解法，会让这道题变得异常简单。还记得 吗？求一个直方图矩形的最大面积。

大家可以先做 84 题，然后回来考虑这道题。

再想一下这个题，看下边的橙色的部分，这完全就是上一道题呀！

算法有了，就是求出每一层的 heights[] 然后传给上一题的函数就可以了。

利用上一题的栈解法。

时间复杂度：O（mn）。

空间复杂度：O（n）。

利用上一题的解法四。

时间复杂度：O（mn）。

空间复杂度：O（n）。

解法三

解法二中套用的栈的解法，我们其实可以不用调用函数，而是把栈糅合到原来求 heights 中。因为栈的话并不是一次性需要所有的高度，所以可以求出一个高度，然后就操作栈。

时间复杂度：O（mn）。

空间复杂度：O（n）。

里边有一个小技巧， 的栈解法中，我们用了两个 while 循环，第二个 while 循环用来解决遍历完元素栈不空的情况。其实，我们注意到两个 while 循环的逻辑完全一样的。所以我们可以通过一些操作，使得遍历结束后，依旧进第一个 while 循环，从而剩下了第 2 个 while 循环，代码看起来会更简洁。

那就是 heights 多申请一个元素，赋值为 0。这样最后一次遍历的时候，栈顶肯定会大于当前元素，所以就进入了第一个 while 循环。

解法四 动态规划

解法二中，用了 84 题的两个解法，解法三中我们把栈糅合进了原算法，那么另一种可以一样的思路吗？不行！因为栈不要求所有的高度，可以边更新，边处理。而另一种，是利用两个数组， leftLessMin [ ] 和 rightLessMin [ ]。而这两个数组的更新，是需要所有高度的。

解法二中，我们更新一次 heights，就利用之前的算法，求一遍 leftLessMin [ ] 和 rightLessMin [ ]，然后更新面积。而其实，我们求 leftLessMin [ ] 和 rightLessMin [ ] 可以利用之前的 leftLessMin [ ] 和 rightLessMin [ ] 来更新本次的。

我们回想一下 leftLessMin [ ] 和 rightLessMin [ ] 的含义， leftLessMin [ i ] 代表左边第一个比当前柱子矮的下标，如下图橙色柱子时当前遍历的柱子。rightLessMin [ ] 时右边第一个。

left 和 right 是对称关系，下边只考虑 left 的求法。

如下图，如果当前新增的层全部是 1，当然这时最完美的情况，那么 leftLessMin [ ] 根本不需要改变。

然而事实是残酷的，一定会有 0 的出现。

我们考虑最后一个柱子的更新。上一层的 leftLessMin = 1，也就是蓝色 0 的位置是第一个比它低的柱子。但是在当前层，由于中间出现了 0。所以不再是之前的 leftLessMin ，而是和上次出现 0 的位置进行比较（因为 0 一定比当前柱子小），谁的下标大，更接近当前柱子，就选择谁。上图中出现 0 的位置是 2，之前的 leftLessMin 是 1，选一个较大的，那就是 2 了。

时间复杂度：O（mn）。

空间复杂度：O（n）。

总

有时候，如果可以把题抽象到已解决的问题当中去，可以大大的简化问题，很酷！

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情