Maximal Rectangle

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

T:
We can treat each row and its above elements as a histogram. The height of the histogram for each row is the number of continues '1's in its above elements. Then we can use the Largest Rectangle in Histogram method to calculate the area of each row.


A:

class Solution {
public:
    int maximalRectangle(vector< vector< char > > &matrix) {
        if(matrix.size() == 0) {
            return 0;
        }
        if(matrix[0].size() == 0) {
            return 0;
        }
        vector< vector< int > > height(matrix.size(), vector< int >(matrix[0].size(), 0));
        for(int j=0; j < matrix[0].size(); j++) {
            for(int i=0; i < matrix.size(); i++) {
                if(matrix[i][j] == '0') {
                    height[i][j] = 0;
                } else if(i==0) {
                    height[i][j] = 1;
                } else {
                    height[i][j] = height[i-1][j] + 1;
                }
            }
        }
        int maxarea = 0;
        for(int i=0; i < height.size(); i++) {
            stack st;
            for(int j=0; j < height[i].size(); j++) {
                if(st.empty() || height[i][st.top()] < height[i][j]) {
                    st.push(j);
                } else {
                    int tmp = st.top();
                    st.pop();
                    maxarea = max(maxarea, (int)(height[i][tmp]*(st.empty()?j:(j-st.top()-1))));
                    j--;
                }
            }
            while(!st.empty()) {
                int tmp = st.top();
                st.pop();
                maxarea = max(maxarea, (int)(height[i][tmp]*(st.empty()?height[i].size():(height[i].size()-st.top()-1))));
            }
        }
        return maxarea;
    }
};