在0-1矩阵中找到最大的1的面积存在问题。在此问题中有两种情况：
要测量的面积是正方形。这个比较简单，可以用DP解决。
要测量的面积是矩形。我无法想出一个最优解。
例子：
010101
101001
111101
110101
最大的矩形面积为4（第3行，第5列以及第3、4行中的另一个）。我们能否获得所有这些矩形？
6个回答
28
我会逐步介绍一些逐渐增加难度/减少运行时间复杂度的解决方案。
首先是暴力解法。生成每个可能的矩形。可以通过迭代每对点（r1，c1）（r2，c2）并满足r1≤r2和c1≤c2（可以用4个for循环完成）来实现此操作。如果矩形不包含0，则将其面积与迄今为止找到的最大面积进行比较。这是O（R ^ 3C ^ 3）。
我们可以将有效矩形检查加速到O（1）。我们通过执行DP来实现这一点，其中dp（r，c）存储矩形中0的数量（（1，1），（r，c））。
- 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]的意思是计算一个矩形内0的个数，其中r1、c1、r2、c2分别为矩形的左上角和右下角的行列坐标。
你可以通过nzeroes(r1,c1,r2,c2) == 0来检查一个矩形是否有效。
有一种O(R^2C)的解决方案，使用简单的DP和堆栈。该DP按列工作，通过找到下一个0之前的单元格上方的1单元格数量来找到每列中的1单元格数量。dp如下所示：
- dp(r, 0) = 0
- 如果matrix[r][c] == 0，则dp(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
- 如果 matrix[r][c] == 0，则 h(r, c) = 0
否则 h(r, c) = h(r-1, c)+1
l(r, 0) = 0
- 如果 matrix[r-1][c] == 0，则 l(r, c) = c-p
否则 l(r, c) = min(l(r-1, c), c-p)
r(r,C+1) = 0
- 如果 matrix[r-1][c] == 0，则 r(r,c) = p-c
- 否则 r(r,c) = min(r(r-1, c), p-c)
其中，p 是我们从左到右填充 l 和从右到左填充 r 时前一个 0 所在的列。
答案为：
- max_r,c(h(r, c) ∗ (l(r, c) + r(r, c) − 1))
注意：我从我写的一个答案here中改编了上述内容——请参阅“Ben's Mom”部分。在那篇文章中，0表示树木。那篇文章的格式也更好。
- moinudin
1
非常感谢。解决方案很棒。 - arun_gopalan
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计算该直方图中最大矩形面积。
- Yash
1
我会尝试以下方法：
(1) 通过 BFS 将矩阵分解为连通组件。
(2) 对于每个连通组件，寻找最大矩形。
对于 (2)，我会先寻找垂直矩形：找到每个连续的 (min_y, max_y) 的最大可能宽度，因此可以在该连通组件的该行中 O(1) 地迭代地查看 1 的最小/最大值来计算面积。 然后我会转置矩阵，并重复该过程。
总运行时间为 O(MxN) 用于 BFS，然后对于每个连通组件，宽度和高度的平方和为 O(width^2 + height^2)，总共为 O(MXN + M^2 + N^2)。
不过我想知道渐进最优解是什么。
(1) 通过 BFS 将矩阵分解为连通组件。
(2) 对于每个连通组件，寻找最大矩形。
对于 (2)，我会先寻找垂直矩形：找到每个连续的 (min_y, max_y) 的最大可能宽度，因此可以在该连通组件的该行中 O(1) 地迭代地查看 1 的最小/最大值来计算面积。 然后我会转置矩阵，并重复该过程。
总运行时间为 O(MxN) 用于 BFS，然后对于每个连通组件，宽度和高度的平方和为 O(width^2 + height^2)，总共为 O(MXN + M^2 + N^2)。
不过我想知道渐进最优解是什么。
- Guy Adini
1
你能详细说明一下吗？ - RATHI
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;
}
}
- HeadAndTail
1
考虑到这是一个老问题，请解释您的代码，并解释它与已有答案的区别。 - Nic3500
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;
}
- Shyam
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;
}
}
- Nidhi Jain
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接