二维矩阵中1的最大矩形
在0-1矩阵中找到1的最大面积有个问题。 在这个问题中有两种情况：
要测量的区域是正方形的。 DP很简单。
要测量的区域是矩形的形状。 我无法为此考虑最佳解决方案。
例：
010101
101001
111101
110101
最大的矩形区域为4（第3行，第5列，第3行第4行）。 我们也可以得到所有这些矩形吗？
我将介绍一些增加难度/降低运行时复杂度的解决方案。
首先，一个蛮力解决方案。 生成每个可能的矩形。 你可以通过遍历每一对点（r1，c1）（r2，c2）来做到这一点，r1≤r2和c1≤c2（可以用4 for循环完成）。 如果矩形不包含0，则将该区域与迄今为止找到的最大区域进行比较。 这是一个O（R ^ 3C ^ 3）。
我们可以将有效的矩形检查加速到O（1）。 我们通过做一个DP，其中dp（r，c）存储矩形（（1，1），（r，c））中的0的数量。
然后（（r1，c1），（r2，c2））中的0的个数为
然后你可以检查一个矩形是否由nzeroes（r1，c1，r2，c2）== 0有效。
有一个O（R ^ 2C）解决方案使用简单的DP和堆栈。 DP每列工作，找到一个单元格上方的1个单元格的数量，直到下一个0. dp如下所示：
如果矩阵[r] [c] = 0，dp（r，0）= 0 dp（r，c）= 0否则dp（r，c）= dp
然后您执行以下操作：
area = 0
for each row r:
stack = {}
stack.push((height=0, column=0))
for each column c:
height = dp(r, c)
c1 = c
while stack.top.height > height:
c1 = stack.top.column
stack.pop()
if stack.top.height != height:
stack.push((height=height, column=c1))
for item in stack:
a = (c - item.column + 1) * item.height
area = max(area, a)
也可以使用三个DP来解决O（RC）中的问题：
这三种复发关系是：
h（r，c）= h（r-1，c）+1否则
l（r，0）= 0
l（r，c）= min（l（r-1，c），c - p）
r（r，C + 1）= 0
其中p是前一个0的列，因为我们从左到右填充l，从右到左填充r。
答案是：
这是有效的，因为观察到最大的矩形总是在所有四条边上都接触0（考虑边缘被0覆盖）。 通过考虑至少顶部，左侧和右侧接触0的所有矩形，我们覆盖所有候选矩形。 生成每个可能的矩形。 你可以通过遍历每一对点（r1，c1）（r2，c2）来做到这一点，r1≤r2和c1≤c2（可以用4 for循环完成）。 如果矩形不包含0，则将该区域与迄今为止找到的最大区域进行比较。
注意：我根据我在这里写的答案调整了上述内容 - 请参阅“本的妈妈”一节。 在那篇文章中，0是树。 该写法也有更好的格式。
问题可以简化为直方图中最大的矩形区域多次。
每行之后，计算直到该行为止建立的直方图，并计算该直方图中的最大面积矩形。
int maximalRectangle(vector<vector<char> > &mat) {
int rows=mat.size();
if(rows==0)return 0;
int columns = mat[0].size();
int temp[columns];
for(int i=0;i<columns;i++){
temp[i] = mat[0][i]-'0';
}
int maxArea=0;
maxArea = max(maxArea,maxUtil(temp,columns));
// cout<<"before loopn";
// print1d(temp,columns);
for(int i=1;i<rows;i++){
for(int j=0;j<columns;j++){
temp[j] = (mat[i][j]-'0')?temp[j]+1:0;
}
// cout<<"after iteration : "<<i<<endl;
// print1d(temp,columns);
maxArea = max(maxArea,maxUtil(temp,columns));
// cout<<"maxarea = "<<maxArea<<endl;
}
return maxArea;
}
temp是每个步骤中的直方图，maxutil计算该直方图中的最大矩形区域。
我会尝试以下方法：
（1）将矩阵分解为连通分量（通过BFS）。
（2）对于每个连接的组件，查找最大的矩形。
要做（2），我首先要查找垂直矩形：为每个连续的（min_y，max_y）找到最大可能的宽度，并且因此该区域（迭代地，在每行O（1）中，仅通过查看最小/在连接组件的那一行中最大为1）。 然后，我将转置矩阵，并重复该过程。
对于每个连接的组件，总的运行时间是O（M×N），然后是O（宽度^ 2 +高度^ 2），总共为O（MXN + M ^ 2 + N ^ 2）。
我想知道什么是渐近最佳解决方案。
链接地址: http://www.djcxy.com/p/94609.html