问题
定一个无序矩阵,其中只有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