Я пытаюсь решить задачу максимального прямоугольника из LeetCode.
Моя реализация разделена на две фазы. Первый этап построения таблицы tabrec
. для любых i и j в диапазоне входной матрицы tabrec[i][j]
не определено, если matrix[i][j] == '0'
, иначе записывает максимальное расширение '1'
в четырех направлениях (влево, вправо, вверх, вниз). На втором этапе я вычисляю максимальный прямоугольник, перебирая строки и столбцы. Для каждой строки я могу идентифицировать последовательные 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 случая с большим набором данных.
Я не могу понять проблему. Что-то не так с моим алгоритмом (я думаю, что это правильно) или какие-то ошибки в моей реализации?