16

0-1 マトリックスの 1 の最大面積を見つける問題があります。この問題には、次の 2 つのケースがあります。

  1. 測定する面積は正方形です。それはDPによる簡単なものです。

  2. 測る範囲は長方形です。これに対する最適な解決策を考えることができません。

例：

010101
101001
111101
110101

最大の長方形の面積は 4 です (3 行目、5 列目、3 行目、4 行目にもう 1 つ)。これらのすべての長方形も取得できますか?

4

6 に答える 6

27

難易度を上げたり、ランタイムの複雑さを減らしたりする解決策をいくつか紹介します。

まず、ブルート フォース ソリューションです。可能なすべての長方形を生成します。これを行うには、点 (r1,c1) (r2,c2) のすべてのペアを r1 ≤ r2 および c1 ≤ c2 で反復処理します (4 つの for ループで実行できます)。四角形に 0 が含まれていない場合は、その面積をこれまでに見つかった最大の面積と比較します。これは O(R^3C^3) です。

有効な矩形チェックを O(1) まで高速化できます。これを行うには、dp(r, c) が四角形 ((1, 1), (r, c)) に 0 の数を格納する DP を実行します。

  • dp(r, 0) = 0
  • dp(0, c) = 0
  • dp(r,c) = dp(r−1,c)+dp(r,c−1)−dp(r−1,c−1)+(行列[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 は、次の 0 までセルの上の 1 セルの数を見つけることによって、列ごとに機能します。dp は次のとおりです。

  • dp(r, 0) = 0
  • dp(r, c) = 0 if matrix[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)

3 つの 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) の長方形を右にどれだけ拡張できますか?

3 つの再帰関係は次のとおりです。

  • h(0, c) = 0
  • h(r, c) = 0 if matrix[r][c] == 0

  • h(r, c) = h(r-1, c)+1 それ以外の場合

  • l(r, 0) = 0

  • l(r, c) = cp if 行列[r-1][c] == 0

  • l(r, c) = min(l(r − 1, c), c − p) それ以外の場合

  • r(r,C+1) = 0

  • r(r,c) = pc if matrix[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))

これは、最大の長方形が 4 つの側面すべてで常に 0 に接触する (エッジが 0 で覆われていると見なす) という観察のために機能します。少なくとも上、左、右が 0 に接しているすべての長方形を考慮すると、すべての候補長方形がカバーされます。可能なすべての長方形を生成します。これを行うには、点 (r1,c1) (r2,c2) のすべてのペアを r1 ≤ r2 および c1 ≤ c2 で反復処理します (4 つの for ループで実行できます)。四角形に 0 が含まれていない場合は、その面積をこれまでに見つかった最大の面積と比較します。

注：ここに書いた回答から上記を適応させました-セクション「ベンのお母さん」を参照してください。その記事では、0 は木です。その記事のフォーマットも改善されています。

于 2012-07-14T09:49:28.350 に答える
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 に答える
1

私は次のことを試します：

(1) 行列を連結成分に分解します (BFS を使用)。

(2) 連結要素ごとに、最大の長方形を探します。

(2) を行うには、最初に垂直方向の長方形を探します: 連続する各 (min_y、max_y) の最大可能幅を見つけ、したがって、面積 (繰り返し、行ごとに O(1) で、min/連結成分のその行の最大 1)。次に、行列を転置し、プロセスを繰り返します。

合計実行時間は、BFS の場合は O(MxN)、接続された各コンポーネントの場合は O(幅^2 + 高さ^2)、合計 O(MXN + M^2 + N^2) になります。

しかし、漸近的に最適なソリューションは何だろうか。

于 2012-07-14T08:35:22.847 に答える
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 に答える