085 - Maximal Rectangle 的DP解法

在讨论区看到的，非常精彩的DP，用三个一维数组，分别统计左边界，右边界，以及每一列的高度，
然后计算每一列的高度乘以可以达到的左右边界之差，得到面积，很好的想法！！
原帖链接：Share my DP solution
 
The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).
All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:

left(i,j) = max(left(i-1,j), curleft)………………..curleft can be determined from the current row
right(i,j) = min(right(i-1,j), curright)…………..curright can be determined from the current row
height(i,j) = height(i-1,j) + 1………………………..if matrix[i][j]=='1';
height(i,j) = 0……………………………………………….if matrix[i][j]=='0'

The code is as below. The loops can be combined for speed but I separate them for more clarity of the algorithm.

class Solution {public:
  int maximalRectangle(vector<vector<char> > &matrix) {
    if(matrix.empty())  return 0;
    const int m = matrix.size();
    const int n = matrix[0].size();
    int left[n], right[n], height[n];
    fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
    int maxA = 0;
    for(int i=0; i<m; i++) {
        int cur_left=0, cur_right=n; 
        for(int j=0; j<n; j++) {    // compute height (can do this from either side)
            if(matrix[i][j]=='1') height[j]++; 
            else height[j]=0;
        }
        for(int j=0; j<n; j++) {    // compute left (from left to right)
            if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
            else {left[j]=0; cur_left=j+1;}
        }
        for(int j=n-1; j>=0; j—) {  // compute right (from right to left) 
            if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
            else {right[j]=n; cur_right=j;} 
        }
        // compute the area of rectangle (can do this from either side)
        for(int j=0; j<n; j++)
            maxA = max(maxA,(right[j]-left[j])*height[j]);
    }
    return maxA;
  }};

If you think this algorithm is not easy to understand, you can try this example:

0 0 0 1 0 0 0 
0 0 1 1 1 0 0 
0 1 1 1 1 1 0

The vector "left" and "right" from row 0 to row 2 are as follows
row 0:

l: 0 0 0 3 0 0 0
r: 7 7 7 4 7 7 7

row 1:

l: 0 0 2 3 2 0 0
r: 7 7 5 4 5 7 7 

row 2:

l: 0 1 2 3 2 1 0
r: 7 6 5 4 5 6 7

The vector "left" is computing the left boundary. Take (i,j)=(1,3) for example. On current row 1, the left boundary is at j=2. However, because matrix[1][3] is 1, you need to consider the left boundary on previous row as well, which is 3. So the real left boundary at (1,3) is 3.
I hope this additional explanation makes things clearer.

• solution-sharing
• dp

asked Jan 2 in Maximal Rectangle by morrischen2008 (7,800 points)
edited Apr 22 by morrischen2008

This solution is so clever that I think so hard to understand it. height counts the number of successive '1's above (plus the current one). The value of left & right means the boundaries of the rectangle which contains the current point with a height of value height.
answered Jan 23 by GavinCode (2,510 points)