LeetCode OJ:Maximal Rectangle

最大子矩阵问题

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.empty())return 0;
        int len=matrix[0].size();
        vector<int> H(len);
        vector<int> L(len);
        vector<int> R(len,len);
        int result=0;
        for(int i=0;i<matrix.size();i++){
            int left=0,right=len;
            for(int j=0;j<len;j++){
                if(matrix[i][j]==‘1‘){
                    H[j]++;
                    L[j]=max(L[j],left);
                }
                else{
                    left=j+1;
                    H[j]=0;L[j]=0;R[j]=len;
                }
            }
            for(int j=len-1;j>=0;j--){
                if(matrix[i][j]==‘1‘){
                    R[j]=min(R[j],right);
                    result=max(result,H[j]*(R[j]-L[j]));
                }
                else right=j;
            }
        }
        return result;
    }
};

LeetCode OJ:Maximal Rectangle

原文：http://blog.csdn.net/starcuan/article/details/18732337