Leetcode：最大矩形

Question

我试图从LeetCode解决maximal rectangle problem。

我的实现分为两个阶段。 第一阶段构建表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例大的数据集。

我找不出这个问题。 我的算法有什么问题（我认为是正确的）或者我的实现中有一些错误？

Answer 1

中有你的算法中的错误：

 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语句while循环中。因为有时候，你不需要达到当前行的最后一个。看一个例子：

0 1 1 1 1 
1 1 1 1 0 

答案应该是6，但是你的算法会返回4。

即使有上述变化，它仍然是不正确的。实际上，这个问题最好用DP来解决。搜索最大的二维数组总和以供参考。