题解 | #最大矩形#

1.计算矩阵每行从左到右连续值为1的长度，得到矩阵left (理解成柱状图) 2.将left的每个非零位置，作为矩阵的右下角，从该位置往上找到一个最大矩形。

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @return int整型
     */
    int maximalRectangle(vector<vector<int> >& matrix) {
        // write code here
        int m=matrix.size();
        int ans=0;
        if(m==0)
            return 0;
        int n=matrix[0].size();
        vector<vector<int> > left(m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==1)
                    left[i][j]=(j==0?1:left[i][j-1]+1);
            }
        }
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0)
                    continue;
                int area=left[i][j];
                int width=left[i][j];
                for(int k=i-1;k>=0;k--){
                    width=min(width,left[k][j]);
                    area=max(area,width*(i-k+1));
                }
                ans=max(ans,area);
            }
        }
        return ans;
    }
};