0

LeetCodeの最大四角形の問題を解決しようとしています。

私の実装は 2 つのフェーズに分かれています。最初のフェーズでは、テーブルを作成しますtabrec。入力行列の範囲内の任意の i および j は、 の tabrec[i][j]場合は未定義です。それ以外の場合は、4 方向 (左、右、上、下)matrix[i][j] == '0'の最大拡張を記録します。'1'フェーズ 2 では、行と列を繰り返し処理して最大の四角形を計算します。行ごとに、同じ行で連続する 1 を識別できます。また、以前に作成したテーブルで 1 の行を囲む最小の四角形を見つけることができます。

ここにコードがあります

class Solution {
    struct Rect {
        int l;
        int r;
        int t;
        int b;
    };

public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int row = matrix.size();
        int col = 0;
        if (row) col = matrix[0].size();

        if (!(row && col)) return 0;

        Rect *storage = new Rect[row * col];
        Rect **rectab = new Rect*[row];

        for (int i = 0; i < row; i++)
            rectab[i] = storage + i * col;

        // find the left most 1-extension for each point
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == '1') rectab[i][0].l = 0;
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == '1') {
                    if (matrix[i][j - 1] == '1')
                        rectab[i][j].l = rectab[i][j - 1].l;
                    else
                        rectab[i][j].l = j;
                }
            }
        }
        // find the right most 1-extension for each point
        for (int i = 0; i < row; i++) {
            if (matrix[i][col - 1] == '1') rectab[i][col - 1].r = col - 1;
            for (int j = col - 2; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    if (matrix[i][j + 1] == '1') rectab[i][j].r = rectab[i][j + 1].r;
                    else rectab[i][j].r = j;
                }
            }
        }
        // find the top most 1-extension for each point
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == '1') rectab[0][j].t = 0;
            for (int i = 1; i < row; i++) {
                if (matrix[i][j] == '1') {
                    if (matrix[i - 1][j] == '1') rectab[i][j].t = rectab[i - 1][j].t;
                    else rectab[i][j].t = i;
                }
            }
        }
        // find the bottom most 1-extension for each point
        for (int j = 0; j < col; j++) {
            if (matrix[row - 1][j] == '1') rectab[row - 1][j].b = row - 1;
            for (int i = row - 2; i >= 0; i--) {
                if (matrix[i][j] == '1') {
                    if (matrix[i + 1][j] == '1') rectab[i][j].b = rectab[i + 1][j].b;
                    else rectab[i][j].b = i;
                }
            }
        }

        int max = 0;
        int i = 0;
        int j = 0;
        while (i < row) {
            while (j < col && matrix[i][j] == '0') j++;
            if (j < col) {
                int el = rectab[i][j].l;
                int er = rectab[i][j].r;
                int et = rectab[i][j].t;
                int eb = rectab[i][j].b;
                j++;
                while (j < col && matrix[i][j] == '1') {
                    Rect *rect = &rectab[i][j];
                    if (el < rect->l) el = rect->l;
                    if (er > rect->r) er = rect->r;
                    if (et < rect->t) et = rect->t;
                    if (eb > rect->b) eb = rect->b;

                    j++;
                }

                if (max < (er - el + 1) * (eb - et + 1))
                    max = (er - el + 1) * (eb - et + 1);

                if (j == col) {
                    i++;
                    j = 0;
                }
            } else {
                i++;
                j = 0;
            }
        }

        delete [] storage;
        delete [] rectab;

        return max;
    }
};

この実装は、小さなデータセットのテストに合格できますが、大きなデータセットでは 4 つのケースで失敗します。

問題がわかりません。アルゴリズムに何か問題がありますか (正しいと思います)、実装にバグがありますか?

4

1 に答える 1

0

アルゴリズムにバグがあります:

        while (j < col && matrix[i][j] == '1') {
            Rect *rect = &rectab[i][j];
            if (el < rect->l) el = rect->l;
            if (er > rect->r) er = rect->r;
            if (et < rect->t) et = rect->t;
            if (eb > rect->b) eb = rect->b;

            j++;
        }

        if (max < (er - el + 1) * (eb - et + 1))
            max = (er - el + 1) * (eb - et + 1);

ここで、while ループの中に if 文を入れる必要があります。場合によっては、現在の行の最後の 1 行に到達する必要がないからです。例を参照してください。

0 1 1 1 1
1 1 1 1 0

答えは 6 のはずですが、アルゴリズムは代わりに 4 を返します。

上記の変更を行っても、まだ正しくありません。実際、この問題は DP を使用して解決する方が適切です。参照用に最大の 2 次元配列合計を検索します。

于 2013-08-03T15:51:29.773 に答える