程序员代码面试指南 1.9：求最大子矩阵的大小（单调栈）

1、思路

• 用一个height数组来统计以当前行作为底的情况下，每个位置往上的1的数量；
• 使用单调栈的方法遍历height数组进栈，栈中存放height数组元素的下标，目的是寻找数组中每个元素向左右两边最大能扩展的距离（即找到左右两边第一个比它小的数）；
• 利用单调栈计算矩阵每一行所代表的height数组，求出其中每个元素向左右两边扩展能达到的最大面积，取最大值。

2、代码

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int maxRecFromBottom(vector<int>& height)   
{
    if (height.empty()) return 0;

    int maxArea = 0;
    stack<int> stk;

    //left与right分别代表左右方向上能够扩展的边界
    for (int right = 0; right < height.size(); ++ right)    
    {
        while (!stk.empty() && height[right] <= height[stk.top()])
        {
            int i = stk.top();                  //要求的是以i位置的点左右扩展的面积，i的右边界为right
            stk.pop();
            int left = stk.empty() ? -1 : stk.top();        //i的左边界left为栈中下一个元素
            int curArea = (right - left - 1) * height[i];   //计算i这个位置展开的面积
            maxArea = max(maxArea, curArea);
        }

        stk.push(right);
    }

    while (!stk.empty())
    {
        int i = stk.top();
        stk.pop();
        int left = stk.empty() ? -1 : stk.top();
        //右边已经没有比它小的值了，故右边界为数组的长度
        int curArea = (height.size() - left - 1) * height[i];   
        maxArea = max(maxArea, curArea);
    }

    return maxArea;
}

int maxRecSize(vector<vector<int>>& map)
{
    if (map.empty()) return 0;

    int maxArea = 0;
    vector<int> height(map[0].size());

    for (int i = 0; i < map.size(); ++ i)                       //计算height数组
    {
        for (int j = 0; j < map[0].size(); ++ j)
        {
            height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
        }

        maxArea = max(maxArea, maxRecFromBottom(height));
    }

    return maxArea;
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> map(n, vector<int>(m));

    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < m; ++ j)
        {
            cin >> map[i][j];
        }
    }

    cout << maxRecSize(map) << endl;

    return 0;
}