2019牛客暑期多校（第二场） H题 悬线法or单调栈

Second Large Rectangle

悬线法用来求解最大子矩形问题

通过悬线法，可以找到以点（i，j）为底的极大矩形。

u[i][j]、l[i][j]、r[i][j]分别表示以为底的极大矩形的上边界，左边界，右边界；

首先预处理：找到点（i，j）可以沿伸的的上端点、左端点，右端点 （dp）

For i = 1 to n
    For j = 1 to m
        u[i][j] = (i-1,j)==1 ? u[i-1][j] : i;
        l[i][j] = (i,j-1)==1 ? l[i][j-1] : j;
    For j = m to 1
        r[i][j] = (i,j+1)==1 ? r[i][j+1] : j;

如图找到了（4,3）  的   上端点、左端点，右端点，但是这些边界并没有组成一个矩形，可以（4,3）的上端点为上边界，找到左右边界，这样就可以找到一个以点（4，3）为底、以点（4，3）上界为高的极大矩形。

For i = 1 to n
    For j = 1 to m
        if (i-1,j)==1
            l[i][j] = max(l[i][j], l[i-1][j]
            r[i][j] = min(r[i][j], r[i-1][j]

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3+100;

int n, m;
int g[N][N];
int u[N][N];
int l[N][N];
int r[N][N];
int hh,ll,rr,bb;
char str[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%s",str+1);
        for(int j =1;j<=m;j++ ){
            if(str[j] == '1') g[i][j] = 1;
            else g[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            u[i][j] = l[i][j] = r[i][j] = 0;
    
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(g[i][j] == 0)    continue;
                u[i][j] = g[i-1][j] == 1 ? u[i-1][j] : i;
                l[i][j] = g[i][j-1] == 1 ? l[i][j-1] : j;
        }
        for(int j = m; j >= 1; j--){
            if(g[i][j] == 0)    continue;
            r[i][j] = g[i][j+1] == 1 ? r[i][j+1] : j;
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(g[i][j] == 0)    continue;
            if(g[i-1][j] == 1){
                l[i][j] = max(l[i][j], l[i-1][j]);
                r[i][j] = min(r[i][j], r[i-1][j]);
            }
            if(ans<(r[i][j]-l[i][j]+1)*(i-u[i][j]+1)){
                hh = u[i][j] , bb =i;
                rr = r[i][j],ll=l[i][j];
                ans = (r[i][j]-l[i][j]+1)*(i-u[i][j]+1);
            }
        }
    }
    int ans2 = 0;
    ans2= max(ans2,(rr - ll) * (bb - hh + 1));
    ans2= max(ans2,(rr - ll +1) * (bb - hh ));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(g[i][j] == 0)    continue;
            if(hh==u[i][j]&&bb==i&&ll==l[i][j]&&rr==r[i][j])
                continue;
            if(ans2<(r[i][j]-l[i][j]+1)*(i-u[i][j]+1)){
                ans2=(r[i][j]-l[i][j]+1)*(i-u[i][j]+1);
            }
        }
    }
    cout << ans2 << endl;
    return 0;
}

单调栈解法：
	

		
	

h[i][j] 表示，点（i，j）到上界的高度，

对于行 i ，通过单调栈对点（i，j）的高度进行处理，可以得到该高度可以形成矩形的左右边界 l[i][j] , r[i][j] ；

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+100;
int n, m;
char str[N][N];
int h[N][N];
int l[N][N],r[N][N];
stack<int> s;
int hh,bb,rr,ll;
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%s", str[i]+1);
    }
    int ans = 0;
    for(int i = 1;i <= n; i++){
        for(int j = 1;j <= m; j++){
            if(str[i][j] == '1')
                h[i][j] = h[i-1][j] + 1;
            else
                h[i][j] = 0;
        }
        
        for(int j = 1;j <= m; j++){
            while(!s.empty() && h[i][j]<h[i][s.top()]){
                r[i][s.top()] = j; s.pop();
            }
            if(!s.empty()){
                if(h[i][j]==h[i][s.top()]) 
                    l[i][j] = l[i][s.top()];
                else l[i][j] = s.top();
            }
            else l[i][j] = 0;
            s.push(j);
        }
        while(!s.empty()){
            r[i][s.top()] = m+1; s.pop();
        }
        for(int j = 1;j <= m; j++){
            if(ans < h[i][j]*(r[i][j]-l[i][j]-1)){
                hh=h[i][j], bb=i, rr=r[i][j], ll=l[i][j];
                ans = h[i][j]*(r[i][j]-l[i][j]-1);
            }
        }
    }
    int ans2 = 0;
    ans2=max(ans2,hh*(rr-ll-2));
    ans2=max(ans2,(hh-1)*(rr-ll-1));
    for(int i = 1;i <= n; i++){
        for(int j = 1;j <= m; j++){
            if(hh==h[i][j]&&bb==i&&rr==r[i][j]&&ll==l[i][j])
                continue;
            ans2 = max(ans2,h[i][j]*(r[i][j]-l[i][j]-1));
        }
    }
    cout << ans2 << endl;
    return 0;
}