ฉันกำลังพยายามแก้ไขปัญหาสี่เหลี่ยมผืนผ้าสูงสุดจาก 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 กรณี
ฉันไม่สามารถเข้าใจปัญหาได้ มีอะไรผิดปกติกับอัลกอริทึมของฉัน (ฉันคิดว่าถูกต้อง) หรือมีข้อบกพร่องในการใช้งานของฉัน