在0-1矩阵中求1的最大面积是有问题的。在这个问题中，有两种情况：
待测面积为正方形。DP很简单。
待测面积为长方形。我无法为此想出最佳解决方案。
例子：
010101
101001
111101
110101
最大的矩形面积为 4（第 3 行，第 5 列，第 3、4 行还有一个）。我们也可以得到所有这些矩形吗？
问问题
19568 次
6 回答
27
我将逐步介绍一些增加难度/降低运行时复杂性的解决方案。
首先，蛮力解决方案。生成每个可能的矩形。您可以通过迭代每对点 (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 的数量。
- dp(r, 0) = 0
- dp(0, c) = 0
- dp(r,c) = dp(r−1,c)+dp(r,c−1)−dp(r−1,c−1)+(matrix[r][c]?0:1)
那么 ((r1, c1), (r2, c2)) 中 0 的个数为
- nzeroes(r1,c1,r2,c2) = dp[r2][c2]−dp[r1 −1][c2]−dp[r2][c1 −1]+dp[r1 −1][c1 −1]
然后，您可以通过 nzeroes(r1,c1,r2,c2) == 0 检查矩形是否有效。
有一个使用简单 DP 和堆栈的 O(R^2C) 解决方案。DP 每列工作，通过查找一个单元格上方的 1 个单元格的数量直到下一个 0。dp 如下：
- dp(r, 0) = 0
- dp(r, c) = 0 如果矩阵[r][c] == 0
- dp(r, c) = dp(r-1, c) + 1 否则
然后执行以下操作：
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)：如果我们从 (r, c) 开始向上走，我们在第一个 0 之前找到多少个 1 单元格？
- l(r, c)：我们可以将一个右下角为 (r, c) 且高度为 h(r, c) 的矩形向左延伸多远？
- r(r,c)：我们可以将左下角位于 (r, c) 且高度为 h(r, c) 的矩形向右延伸多远？
三个递归关系是：
- h(0, c) = 0
- h(r, c) = 0 如果矩阵[r][c] == 0
h(r, c) = h(r-1, c)+1 否则
l(r, 0) = 0
- l(r, c) = cp 如果矩阵[r-1][c] == 0
l(r, c) = min(l(r - 1, c), c - p) 否则
r(r,C+1) = 0
- r(r,c) = pc 如果矩阵[r-1][c] == 0
- r(r,c) = min(r(r - 1, c), p - c) 否则
其中 p 是前一个 0 的列，因为我们从左右填充 l，从左右填充 r。
那么答案是：
- max_r,c(h(r, c) ∗ (l(r, c) + r(r, c) − 1))
这是因为观察到最大的矩形总是在所有四个边上都接触到 0（考虑到边缘被 0 覆盖）。通过考虑至少顶部、左侧和右侧接触 0 的所有矩形，我们覆盖了所有候选矩形。生成每个可能的矩形。您可以通过迭代每对点 (r1,c1) (r2,c2) 来做到这一点，其中 r1 ≤ r2 和 c1 ≤ c2 （可以用 4 个 for 循环完成）。如果矩形不包含 0，则将该区域与目前找到的最大区域进行比较。
注意：我根据我在这里写的答案改编了上述内容 - 请参阅“本的妈妈”部分。在那篇文章中，0 是树。那篇文章也有更好的格式。
于 2012-07-14T09:49:28.350 回答
1
我会尝试以下方法：
(1) 将矩阵分解为连通分量（通过 BFS）。
(2) 对于每个连通分量，寻找最大矩形。
要执行 (2)，我将首先查找垂直矩形：查找每个连续 (min_y, max_y) 的最大可能宽度，因此只需查看 min/连接组件的该行中最多为 1）。然后我会转置矩阵，并重复这个过程。
BFS 的总运行时间为 O(MxN)，然后每个连接的组件为 O(width^2 + height^2)，总共为 O(MXN + M^2 + N^2)。
我想知道什么是渐近最优解。
于 2012-07-14T08:35:22.847 回答
1
该问题可以简化为多次在直方图中找到最大矩形区域。
在每一行之后，您计算在该行之前构建的直方图，并计算该直方图中的最大面积矩形。
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 loop\n";
// 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 计算该直方图中的最大矩形面积。
于 2014-04-13T07:27:47.080 回答
0
使用这种动态规划方法
- 该问题可以简化为多次在直方图中找到最大矩形区域。
- 在每一行之后，您计算在该行之前构建的直方图，并计算该直方图中的最大面积矩形。
**
import java.util.Scanner;
public class LargestRectInAmatrix {
static int row, col, matrix[][];
static int maxArea = 0;
static int barMatrix[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
row = sc.nextInt();
col = sc.nextInt();
matrix = new int[row][col];
barMatrix = new int[col];
for(int i = 0; i < row ; i++) {
for(int j = 0 ; j < col ; j++) {
matrix[i][j] = sc.nextInt();
}
}
startSolution();
System.out.println(maxArea);
}
private static void startSolution() {
for(int i = 0 ; i < row ; i++) {
for(int j = 0 ; j < col ; j++) {
if(matrix[i][j] == 0) {
barMatrix[j] = 0;
}
else
barMatrix[j]=barMatrix[j]+matrix[i][j];
}
int area = calculateArea(0, col-1);
if(area > maxArea) {
maxArea = area;
}
}
}
private static int calculateArea(int l,int h)
{
if(l > h) {
return Integer.MIN_VALUE;
}
if(l == h) {
return barMatrix[l];
}
int u = calMinimumIndex(l,h);
return (max(calculateArea(l, u-1), calculateArea(u+1, h), barMatrix[u] * (h - l + 1)));
}
private static int max(int a, int b, int c) {
if(a > b) {
if(a > c) {
return a;
}
else
return c;
}
else
if(b > c) {
return b;
}
else
return c;
}
private static int calMinimumIndex(int l, int h) {
int min=Integer.MAX_VALUE;
int min_index = 0;
for(int i = l ; l <= h ; i++) {
if(barMatrix[i] < min){
min = barMatrix[i];
min_index = i;
}
}
return min_index;
}
}
于 2016-05-22T09:34:19.863 回答
0
另一种更简单的方法是使用两个临时 M x N 数组来计算矩形的长度（行和列） - 即连续 1 的计数。遍历两个临时矩阵以找到最大重复长度（行和列）。
这是相同的代码。
int GetMaxRectangularArea(vector<vector<int>> & matrix, int nRows, int nCols)
{
vector<vector<int>> rowLengths(nRows, vector<int>(nCols));
vector<vector<int>> colLengths(nRows, vector<int>(nCols));
// initialize first column of rowLengths with first column of matrix
for (int i = 0; i < nRows; i++) {
rowLengths[i][0] = matrix[i][0];
}
// initialize first row of colLengths with first row of matrix
for (int j = 0; j < nCols; j++) {
colLengths[0][j] = matrix[0][j];
}
// Compute row wise length of consecutive 1's in rowLengths
for (int i = 0; i < nRows; i++) {
for (int j = 1; j < nCols; j++) {
if (matrix[i][j] == 1) {
rowLengths[i][j] = 1 + rowLengths[i][j - 1];
}
else {
rowLengths[i][j] = 0;
}
}
}
// Compute column wise length of consecutive 1's in colLengths
for (int j = 0; j < nCols; j++) {
for (int i = 1; i < nRows; i++) {
if (matrix[i][j] == 1) {
colLengths[i][j] = 1 + colLengths[i- 1][j];
}
else {
colLengths[i][j] = 0;
}
}
}
// Now traverse the rowLengths array to find max length sub array
int maxArea = 0;
for (int j = nCols - 1; j >= 0; j--) {
int currentArea = 0;
int currentMax = -1;
int repeats = 1;
for (int i = nRows - 1; i >= 0; i--) {
if (rowLengths[i][j] != currentMax) {
if (currentMax != -1) {
currentArea = currentMax * repeats;
if (currentArea > maxArea) {
maxArea = currentArea;
}
}
currentMax = rowLengths[i][j];
repeats = 1;
}
else {
repeats++;
}
}
currentArea = currentMax * repeats;
if (currentArea > maxArea) {
maxArea = currentArea;
}
}
for (int i = nRows - 1; i >= 0; i--) {
int currentArea = 0;
int currentMax = -1;
int repeats = 1;
for (int j = nCols - 1; j >= 0; j--) {
if (colLengths[i][j] != currentMax) {
if (currentMax != -1) {
currentArea = currentMax * repeats;
if (currentArea > maxArea) {
maxArea = currentArea;
}
}
currentMax = colLengths[i][j];
repeats = 1;
}
else {
repeats++;
}
}
currentArea = currentMax * repeats;
if (currentArea > maxArea) {
maxArea = currentArea;
}
}
return maxArea;
}
于 2016-10-23T14:41:43.243 回答
0
class GfG{
public int maxArea(int a[][],int m,int n){
if(a==null || m==0 || n== 0) return 0;
m = a.length;
n = a[0].length;
int dp[] = new int[n+1];
int height[] = new int[n];
int p = 0;
dp[p] = -1;
int ans = 0;
//System.out.println("1 ");
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(a[i][j]==1){
height[j] += a[i][j];
}
else{
height[j] = 0;
}
}
p= 0;
//System.out.println("2 ");
for(int j = 0;j<n;j++){
while(p>0 && height[j] < height[dp[p]]){
int start = dp[p-1];
ans = Math.max(ans,(j-start-1)*height[dp[p]]);
p--;
//System.out.println("1 ");
}
dp[++p] = j;
}
}
return ans;
}
}
于 2017-12-27T05:26:09.853 回答