最大子矩阵

· · 算法·理论

给出一个 n\times m 的矩阵，这个矩阵中有 s 个障碍点，求不包含这些障碍点的最大子矩阵。

单调栈（悬线法）

扫描整个矩阵，时间复杂度为 O(nm)。

例题

P4147 玉蟾宫

考虑以每一行为底边的矩形。用 h_j 表示当前行第 j 列向上延伸的最大高度。用单调栈维护第 j 列左边第一个小于 h_j 的位置 l_j 和右边第一个小于 h_j 的位置 r_j。于是，对于当前行的每一列，就有一个局部最大子矩阵 h_j\times (r_j-l_j-1)，所有局部最大子矩阵就是整个图的最大子矩阵。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,stk[N],tt,h[N],l[N],r[N];
char a[N][N];
int main(){
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=n;i++){
        tt=0;
        stk[++tt]=0;
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='F') h[j]++;
            else h[j]=0;
            while(tt&&h[stk[tt]]>=h[j]) tt--;
            l[j]=stk[tt];
            stk[++tt]=j;
        }
        tt=0;
        stk[++tt]=m+1;
        for(int j=m;j>=1;j--){
            while(tt&&h[stk[tt]]>=h[j]) tt--;
            r[j]=stk[tt];
            stk[++tt]=j;
        }
        for(int j=1;j<=m;j++) ans=max(ans,h[j]*(r[j]-l[j]-1));
    }
    cout<<ans*3;
    return 0;
}

子矩阵计数

P1950 长方形

此题从最大子矩阵问题变为子矩阵计数，其本质其实都是一样的，所以此题也能用单调栈求解。

思路跟上一题差不多，只是有一些小细节需要变化一下：

  1. 从求最大子矩阵面积改为子矩阵计数：(j-l_j)\times h_j\times(r_j-j)；

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,h[N],stk[N],tt,l[N],r[N];
char s[N][N];
long long ans;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i]+1;
    for(int i=1;i<=n;i++){
        tt=0;
        for(int j=1;j<=m;j++){
            if(s[i][j]=='.') h[j]++;
            else h[j]=0;
            while(tt&&h[stk[tt]]>h[j]) tt--;
            if(tt) l[j]=stk[tt];
            else l[j]=0;
            stk[++tt]=j;
        }
        tt=0;
        for(int j=m;j>=1;j--){
            while(tt&&h[stk[tt]]>=h[j]) tt--;
            if(tt) r[j]=stk[tt];
            else r[j]=m+1;
            stk[++tt]=j;
        }
        for(int j=1;j<=m;j++) ans+=1ll*(j-l[j])*h[j]*(r[j]-j);
    }
    cout<<ans;
    return 0;
}

极大化

当矩阵较大时，可以考虑只扫描障碍点，时间复杂度为 O(s^2)。

例题

P1578 奶牛浴场

考虑扫描障碍点。

显然，一个极大子矩阵的边界一定在障碍点上或与整个矩阵的边界重合。

考虑按横坐标从小到大枚举障碍点。为了方便，可以把整个矩阵四个角加入障碍点。先固定左边界，再扫描右边界。上下边界最初定为整个矩阵的上下边界，每次扫描更新上下边界，具体地，若当前点高于最左边的点则更新上边界，反之更新下边界。每次扫描更新答案。

又考虑到上述做法存在遗漏，即左右边界与整个矩阵左右边界存在重合又不包含那四个角的子矩阵，所以我们可以按纵坐标从小到大枚举障碍点，做法与上述做法类似。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int n,m;
struct Node{
    int x,y;
}a[N];
bool cmp1(Node a,Node b){
    return a.x<b.x;
}
bool cmp2(Node a,Node b){
    return a.y<b.y;
}
int main(){
    cin>>n>>m;
    int k;
    cin>>k;
    for(int i=1;i<=k;i++) cin>>a[i].x>>a[i].y;
    int dx[4]={0,n,n,0},dy[4]={m,m,0,0};
    for(int i=k+1;i<=k+4;i++) a[i]={dx[i-k-1],dy[i-k-1]};
    k+=4;
    sort(a+1,a+1+k,cmp1);
    int ans=0;
    for(int i=1;i<=k;i++){
        int up=m,down=0;
        for(int j=i+1;j<=k;j++){
            ans=max(ans,(up-down)*(a[j].x-a[i].x));
            if(a[j].y>a[i].y) up=min(up,a[j].y);
            else down=max(down,a[j].y);
        }
    }
    sort(a+1,a+1+k,cmp2);
    for(int i=1;i<=k;i++){
        int l=0,r=n;
        for(int j=i+1;j<=k;j++){
            ans=max(ans,(r-l)*(a[j].y-a[i].y));
            if(a[j].x>a[i].x) r=min(r,a[j].x);
            else l=max(l,a[j].x);
        }
    }
    cout<<ans;
    return 0;
}