悬线法求最大矩形

矩形"/>

悬线法求最大矩形

悬线法

一 定义

​ 悬线的定义，就是一条竖线，这条竖线要满足上端点在整个矩形上边界或者是一个障碍点。然后以这条悬线进行左右移动，直到移至障碍点或者是矩阵边界，进而确定这条悬线所在的极大矩阵。

二 悬线法的使用

​ 首先我们要得到一个r数组和一个l数组，记录这个点的左边可到达点和这个点的右边可到达点。在用up数组得到这个点的向上最大高度，从而得到最终的解。

三 code

初始化

  for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++)map[i][j] = input(),up[i][j] = 1,r[i][j] = l[i][j] = j;

得到我们的l和r数组

for(int i = 1;i <= n;i++)for(int j = 2;j <= m;j++){if(map[i][j]&&map[i][j-1])l[i][j] = l[i][j-1];}for(int i = 1;i <= n;i++)for(int j = m-1;j >= 1;j--){if(map[i][j]&&map[i][j+1])r[i][j] = r[i][j+1];}

得到up数组并更新答案

for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(i>1&&map[i][j]==1&&map[i-1][j]==1){r[i][j]=min(r[i][j],r[i-1][j]);l[i][j]=max(l[i][j],l[i-1][j]);up[i][j]=up[i-1][j]+1;}ans=max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);}}