Saya mencoba memecahkan masalah persegi panjang maksimal dari LeetCode.
Implementasi saya dipisahkan menjadi dua tahap. Tahap pertama membuat tabel tabrec
. untuk setiap i dan j dalam rentang matriks masukan tabrec[i][j]
tidak ditentukan jika matrix[i][j] == '0'
, jika tidak maka ekstensi maksimum '1'
akan dicatat dalam empat arah (kiri, kanan, atas, bawah). Pada fase kedua, saya menghitung persegi panjang maksimum dengan melakukan iterasi melalui baris dan kolom. Untuk setiap baris, saya dapat mengidentifikasi angka 1 yang berurutan di baris yang sama. Saya juga dapat menemukan persegi panjang minimum yang melingkupi baris 1 dengan tabel yang dibuat sebelumnya.
Ini kodenya
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;
}
};
Implementasi ini dapat lulus pengujian kumpulan data kecil, sementara gagal dalam 4 kasus pada kumpulan data besar.
Saya tidak dapat menemukan masalahnya. Ada yang salah dengan algoritme saya (menurut saya benar) atau ada bug dalam implementasi saya?