Самый большой прямоугольник 1 в 2d двоичной матрице

Ответ 1

Я расскажу о нескольких решениях увеличения сложности/уменьшения сложности во время выполнения.

Во-первых, решение грубой силы. Создайте каждый возможный прямоугольник. Вы можете сделать это, перебирая каждую пару точек (r1, c1) (r2, c2) с r1 ≤ r2 и c1 ≤ c2 (можно сделать с 4 для циклов). Если прямоугольник не содержит 0, вы сравниваете область с самой большой найденной областью. Это O (R ^ 3C ^ 3).

Мы можем ускорить проверку правильности прямоугольника до O (1). Мы делаем это с помощью DP, где dp (r, c) хранит число 0 в прямоугольнике ((1, 1), (r, c)).

• дп (р, 0) = 0
• дп (0, с) = 0
• dp (r, c) = dp (r − 1, c) +dp (r, c − 1) −dp (r − 1, c − 1) + (матрица [r] [c]? 0: 1)

Тогда число 0 в ((r1, c1), (r2, c2)) равно

• 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.

Для этого есть решение O (R ^ 2C) с использованием простого DP и стека. DP работает на каждый столбец, находя количество ячеек над ячейкой до следующего 0. Дп выглядит следующим образом:

• дп (р, 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)

Также можно решить проблему в O (RC), используя три DP:

• h (r, c): если мы начнем с (r, c) и пойдем вверх, сколько 1 клеток мы найдем до первых 0?
• 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 для циклов). Если прямоугольник не содержит 0, вы сравниваете область с самой большой найденной областью.

Примечание: я адаптировал вышеизложенное из ответа, который я написал здесь - обратитесь к разделу "Бен Мама". В этой записи 0 являются деревьями. Эта запись также имеет лучшее форматирование.

Ответ 2

Проблема может быть уменьшена до нахождения максимальной площади прямоугольника в гистограмме несколько раз.

После каждой строки вы вычисляете гистограмму, построенную до этой строки, и вычисляете максимальный прямоугольник области в этой гистограмме.

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 вычисляет максимальную прямоугольную область в этой гистограмме.

Ответ 3

Я бы попробовал следующее:

(1) Разложите матрицу на подключенные компоненты (через BFS).

(2) Для каждого подключенного компонента найдите максимальный прямоугольник.

Чтобы сделать (2), я бы сначала искал вертикальные прямоугольники: найдите максимальную возможную ширину для каждого последовательного (min_y, max_y) и, следовательно, области (итеративно, в O (1) в строке, просто взглянув на min/max 1 в этой строке подключенной компоненты). Затем я перенесу матрицу и повторю процесс.

Общее время работы O (MxN) для BFS, тогда O (ширина ^ 2 + высота ^ 2) для каждого подключенного компонента, для всего O (MXN + M ^ 2 + N ^ 2).

Интересно, что асимптотически оптимальное решение.

Ответ 4

**

//use this dynamic programming approach
//The problem can be reduced to finding the maximum rectangle area in a histogram, multiple times.
After each row, you calculate the histogram built until that row, and that calculate the maximum area rectangle in that histogram.

**

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;
    }


}

Ответ 5

Другим более простым подходом является использование двух массивов temp 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 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 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;
} 

Ответ 6

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;
    }
}