Day 83, #85, Maximal Rectangle

Maximal Rectangle

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

--------------------------------------------
方法1：O(m * n) 解法来自google，借用了上一题Largest Rectangle Area的代码
将每一行都看做x轴，在每一个列上的连续1的个数则为当前列的y值，计算出当前行的最大矩形面积

class Solution {
public:
    // from the question Largest Rectangle Area
    int largestRectangleArea(vector<int> &height) {
        stack<int> st;
        int largest = 0;
        height.push_back(0);
        
        for (int i = 0; i < height.size(); i++) {
            
            if (st.empty() || height[i] >= height[st.top()]) {
                st.push(i);
            }else {
                int topBar = st.top();
                st.pop();
                if (st.empty()) {
                    largest = max(largest,height[topBar] * i);
                }else {
                    largest = max(largest,height[topBar] * (i - st.top() - 1));
                }
                
                i--;
            }
        }

        return largest;
    }

    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size() == 0) return 0;
        vector<int> heights(matrix[0].size(),0);
        int largest = 0;
        
        for (int row = 0; row < matrix.size(); row++) {
            for (int col = 0; col < matrix[0].size(); col++) {
                if (matrix[row][col] == '1') {
                    heights[col]++;
                }else {
                    heights[col] = 0;
                }
            }
            largest = max(largest, largestRectangleArea(heights));
        }
        
        return largest;
    }
};

方法2：O(m * n * m)
dp[i][j]存的是以（i,j）为起点往右，在该行上连续的1的个数

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n + 1,0));
        
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = dp[i][j + 1] + 1;
                }
            }
        }
        
        int largest = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int width = dp[i][j];
                for (int k = i; k < m && width > 0; k++) {
                    width = min(dp[k][j],width);
                    largest = max(largest,width * (k - i + 1));
                }
            }
        }
        
        return largest;
    }
};

方法3：COME_BACK
height[i]是在（i, j）上1的高度，如果matrix[i][j] = 0，则height[i] = 0
left[i]是底边包含(i, j)，高度为height[i]矩阵的最左边的index，right[i]类似
（找个例子，走一边就信服了）

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<int> left(n,0);
        vector<int> right(n,n - 1);
        vector<int> height(n,0);
        int largest = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                }else {
                    height[j] = 0;
                }
            }
            
            int furLeft = 0;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = max(furLeft,left[j]);
                }else {
                    furLeft = j + 1;
                    left[j] = 0;
                }
            }
            
            int furRight = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = min(furRight,right[j]);
                }else {
                    furRight = j - 1;
                    right[j] = n - 1;
                }
            }
            
            for (int j = 0; j < n; j++) {
                largest = max(largest,height[j] * (right[j] - left[j] + 1));
            }
        }
        
        return largest;
    }
};