问题描述

如图所示的仅包含 0，1 元素的二维数组，找出最大的矩形面积。矩形需要满足：内部元素全为 1 (图中的最大矩形面积显然为 6)
问题示意

问题分析

先将问题转化为这样一个问题：柱状图的最大矩阵面积，如下图示意。显然，对于该图而言，最大矩形面积为 10
柱状图最大矩形面积

如何解决柱状图的最大矩形面积问题呢？我们需要从图中找到规律。

首先可以明确：最大矩形面积肯定不小于每个柱体的面积，因此，我们先找到一个方法去计算最大柱体的面积。
最简单的方法肯定就是直接去遍历柱体的高度呗。但这样不具有普遍性，因为对于柱体连接之后所构成的更大的矩形，就不能用这种方法去计算了。

还是以该图举例。对于柱体 6，我们发现其两旁的柱体都低于 6，因此对于该柱体的面积，就等于两边柱体的距离(柱体 5 和柱体 2 的距离)乘以该柱体的高度。

可这个方法对于柱体 5 而言呢？其两旁比它低的柱体分别是柱体 1 和柱体 2，按照这个方法算出来恰好就是我们想要的答案 10！

我们需要一个理由和理解来对这个方法进行支撑。思考之后，给出这样的断言：

计算一个柱状图的最大矩形面积，等价于柱状图的宽度乘以柱状图中最低的柱体

可能有人会问了，拿上图来举例，按这个断言计算出来的答案不就是 6 了吗？(宽度=6，高度=1)。确实如此，但精华就在于，柱状图中的部分柱体(甚至单个柱体)又可以构成子柱状图。所以我们计算最大面积，实际上是去计算所有子柱状图的最大矩形面积，然后取最大值。

这个模式就能够使用单调栈去解决了。

这里给出答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 注意，heights第一个元素和最后一个元素均为0
int getMaxMatrix(vector<int> &heights){
    stack<int> S;
    int len = heights.size();
    int ans = 0;
    for(int i = 0; i < len; ++i){
        while(!S.empty() && heights[S.top()]>heights[i]){
            auto h = heights[S.top()];
            S.pop();
            ans = max(ans, h * (i-S.top()-1));
        }
        S.push(i);
    }
    return ans;
}

问题回归

解决了柱状图的问题，那么对于二维数组的问题，也就迎刃而解了。我们只需要遍历每一行，对于每一行的遍历，都能够得到一个新的柱状图，然后再把柱状图带入到上面的代码中就可以得到答案。最后取最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maximalRectangle(vector<vector<char>>& matrix) {
    int m = matrix.size();
    if(!m)  return 0;
    int n = matrix[0].size();
    if(!n)  return 0;
    vector<int> heights(n+2, 0); // 第一个元素和最后一个元素均为0
    int ans = 0;
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
            heights[j+1] = matrix[i][j]=='1' ? heights[j+1]+1 : 0;
        }
        ans = max(ans, getMaxMatrix(heights));
    }
    return ans;
}