首页 > 其他 > 详细

Maximal Rectangle

时间:2015-09-18 00:45:57      阅读:175      评论:0      收藏:0      [点我收藏+]

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

 

int maximalRectangle(vector<vector<char>>& matrix) {
        
        int m=matrix.size();
        if(m==0)
        return 0;
        int n=matrix[0].size();
        if(n==0)
        return 0;
        int d[m][n]={0},res=0;
        for(int i=0;i<m;i++)
        {
            d[i][0]=matrix[i][0]-0;
            for(int j=1;j<n;j++)
            {
                d[i][j]=matrix[i][j]==1?d[i][j-1]+1:0;
            }
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                res=(res-expand((int*)d,i,j,m,n))>0?res:expand((int*)d,i,j,m,n);
            }
        }
        return res;
        
        
    }
    int expand(int *d,int I,int J,int m,int n)
    {
        //(int(*)[n])d;
        int height=0;
        int wide=*(d+I*n+J);
        for(int i=I-1;i>=0;i--)
        {
            if(*(d+i*n+J)>=wide)
            height++;
            else
            break;
        }
        for(int i=I;i<m;i++)
        {
            if(*(d+i*n+J)>=wide)
            height++;
            else
            break;
        }
        return wide*height;
    }

 

Maximal Rectangle

原文:http://www.cnblogs.com/hexhxy/p/4817980.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!