[step by step]thoughts on the problem
Just like my previous post of the largest area under the histogram.\n\nWe can solve this problem by solve level by level and the sub-problem is just the largest
Just like my previous post of the largest area under the histogram.\n\nWe can solve this problem by solve level by level and the sub-problem is just the largest rectangle under the histogram.\n\nCode:\n\n    class Solution {\n    public:\n        int maximalRectangle(vector<vector<char>>& matrix) {\n            /** largest rectangle based solution **/\n            if(matrix.size()<=0 || matrix[0].size()<=0)\n                return 0;\n            int m=matrix.size();\n            int n=matrix[0].size()+1;\n            int h=0, w=0, result=0;\n            vector<int> height(n, 0);\n            for(int i=0; i<m; i++){\n                stack<int> s;\n                for(int j=0; j<n; j++){\n                    /** update the current row ended height array **/\n                    if(j<n-1){\n                        if(matrix[i][j]=='1')  height[j]+=1;\n                        else height[j]=0;\n                    }\n                    /** use the histogram-max-rectangle-module **/\n                    while(!s.empty() && height[s.top()]>=height[j]){\n                        h=height[s.top()];\n                        s.pop();\n                        w=s.empty() ? j:j-s.top()-1;\n                        if(h*w>result) result=h*w;\n                    }\n                    s.push(j);\n                }\n            }\n            return result;\n        }\n    };
[]