85. Maximal Rectangle (Hard)

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example, given the following matrix:

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

Return 6.

此题是之前那道的 Largest Rectangle in Histogram 直方图中最大的矩形 的扩展，这道题的二维矩阵每一层向上都可以看做一个直方图，输入矩阵有多少行，就可以形成多少个直方图，对每个直方图都调用 Largest Rectangle in Histogram 直方图中最大的矩形 中的方法，就可以得到最大的矩形面积。那么这道题唯一要做的就是将每一层构成直方图，由于题目限定了输入矩阵的字符只有 '0' 和 '1' 两种，所以处理起来也相对简单。方法是，对于每一个点，如果是‘0’，则赋0，如果是 ‘1’，就赋 之前的height值加上1。具体参见代码如下：

Solution 1: stack

int maximalRectangle(vector<vector<char>>& matrix) {
    int area = 0;
    int n = matrix.size();
    if (n == 0) return 0;
    int m = matrix[0].size();
    vector<int> v(m, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            v[j] = matrix[i][j] == '0' ? 0:1+v[j];
        }
        area = max(area, largestRectangleArea(v));
    }
    return area;
}

int largestRectangleArea(vector<int>& heights) {
    heights.push_back(0); // ensure all heights stored in s are checked
    int area = 0, n = heights.size(), end = -1;
    vector<int> s(n);
    for (int i = 0; i < n; ++i) {
        while (end != -1 && heights[s[end]] >= heights[i]) {
            int top = heights[s[end]]; --end;
            // area between i and second tallest height in stack 
            // (excluding)
            area = max(area, top*(end == -1 ? i:i-s[end]-1));
        }
        s[++end] = i;
    }
    return area;
}

combine two functions

int maximalRectangle(vector<vector<char>>& matrix) {
    int area = 0, n = matrix.size();
    if (n == 0) return 0;
    // add one more 0 at the end
    // ensure all heights stored in s are checked
    int m = matrix[0].size()+1; 
    vector<int> heights(m, 0), s(m);

    for (int i = 0; i < n; ++i) {
        int end = -1;
        for (int j = 0; j < m; ++j) {
            if (j < m-1)
                heights[j] = matrix[i][j] == '0' ? 0:1+heights[j];

            while (end != -1 && heights[s[end]] >= heights[j]) {
                int top = heights[s[end]]; --end;
                area = max(area, top*(end == -1 ? j:j-s[end]-1));
            }
            s[++end] = j;
        }
    }
    return area;
}

Solution 2: dp

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), cur_left), cur_left can be determined from the current row

right(i,j) = min(right(i-1,j), cur_right), cur_right 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'

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

int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;
    int res = 0, m = matrix.size(), n = matrix[0].size();
    vector<int> height(n, 0), left(n, 0), right(n, n);
    for (int i = 0; i < m; ++i) {
        int cur_left = 0, cur_right = n;
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') ++height[j];
            else height[j] = 0;
        }
        for (int j = 0; j < n; ++j) {
            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) {
            if (matrix[i][j] == '1') right[j] = min(right[j], cur_right);
            else {right[j] = n; cur_right = j;}
        }
        for (int j = 0; j < n; ++j) {
            res = max(res, (right[j] - left[j]) * height[j]);
        }
    }
    return res;
}

Combine some for loops

int maximalRectangle(vector<vector<char>>& matrix) {

    int n = matrix.size();
    if (n == 0) return 0;
    int m = matrix[0].size(), area = 0;

    vector<int> left(m,0), right(m,m), heights(m,0);
    for (int i = 0; i < n; ++i) {
        int cur_left = 0, cur_right = m;
        // height :
        // left boundary : from left to right
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] == '1') {
                ++heights[j];
                left[j] = max(left[j], cur_left);
            } else {
                heights[j]=0;
                left[j] = 0;
                cur_left = j+1;
            }
        }

        for (int j = m-1; j >= 0; --j) {
            if (matrix[i][j] == '1') right[j] = min(right[j], cur_right);
            else { right[j] = m; cur_right = j; }
            area = max(area, (right[j]-left[j])*heights[j]);
        }

    }
    return area;
}