只含1最大的子矩阵

问题

定一个无序矩阵,其中只有1和0两种值,求只含有1的最大的子矩阵大小,矩阵的大小用其中的元素个数来表示

思路

和前面[子矩阵的最大和 ]不同的是,该矩阵只含0,1两种值。故与求最大子矩阵的遍历过程类似。那么如何找到全为1的子矩阵,如何压缩矩阵成为本题的关键点

如果我们将矩阵中所有的1连成的区域看成一个直方图,我们求该直方图中最大的长方形即是求只含1最大的子矩阵。换一个角度看问题,便使得问题得到了很大的简化。所以我们的程序需要俩个函数,一个将矩阵生成直方图,一个求直方图中最大长方形面积

我们运用之前压缩的思想,将矩阵压缩成一个height高度数组,每个数组元素值的含义就是该位置上面连续个1的个数,即是直方图的高度。这里的压缩策略,不能再是简单的单列累加求和。只要该位置处为0,则该列的高度为0

直方图中最大长方形面积,我们借助栈结构来实现。通过查找当前位置左右边界(就是离它最近的小于等于当前位置元素值的位置)。由左右边界可得到长方形的底边长,再乘以当前元素值(长方形的宽),于是就得到,含有当前元素的最大长方形的大小。

进栈出栈策略
为了取到左右边界的位置,压入元素的index。第一个元素(0)直接进栈,栈底元素的左边界为-1
当前元素 > 栈顶元素, 入栈
当前元素 <= 栈顶元素, 出栈,开始结算栈顶元素的左右边界

结算边界策略
当前元素,即为栈顶元素的右边界。栈顶下面的元素一定是栈顶元素的左边界。由于出栈策略,保证了它们是第一个小于等于栈顶的元素

有一个值得注意的地方是,如果当前元素等于栈顶元素,此时并不能确定栈顶元素的右边界。因为可能后面还有大于等于栈顶元素,那么右边界就可以继续向下扩充。那么根据前面的边界结算规则就会得到错误的右边界。但这并不影响最大长方形的查找。我们只需用当前元素替换更新栈顶元素,最后一个相等值一定是正确的

由于一些栈内元素暂时没找到右边界,故数组遍历完成,栈不为空。这时需要我们逐一弹出栈内元素,并一一计算它们的子长方形面积。因为数组已经遍历完成,故将它们的右边界都设为length

int maxRecFromBottom(int *height)
{
    if (height == NULL || line == 0)
    {
        return 0;
    }
    int maxArea = 0;
    int l = 0;
    int r = 0;
    int h = 0;
    stack<int> s;
    s.push(0);
    for (int i = 1; i < line; ++i)
    {
        while (!s.empty() && height[i] <= height[s.top()])
        {
            h = s.top();
            s.pop();
            r = i;
            l = s.empty() ? -1 : s.top();
            maxArea = max(maxArea, (r - l - 1) * height[h]);
        }
        s.push(i);
    }
    while (!s.empty())
    {
        int h = s.top();
        s.pop();
        l = s.empty() ? -1 : s.top();
        maxArea = max(maxArea, (line - l - 1) * height[h]);
    }
    return maxArea;
}
int maxRecSize(int map[][line])
{
    if (map == NULL || row == 0 || line == 0)
    {
        return 0;
    }
    int res = 0;
    int height[line];
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < line; ++j)
        {
            //生成height数组
            height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
        }
        res = max(res, maxRecFromBottom(height));
    }
    return res;
}

只要当前栈顶小于当前元素,就要不断地弹出结算待结算完成后,将当前元素的index压入栈内。
while (!s.empty() && height[i] <= height[s.top()])

子长方形面积为两边界内的部分,故其长度为r - l - 1