单调栈求最大全1矩形

给定一个01矩阵，在O(nm)时间内，求出其中面积最大的一个全1矩形
例题goto

思路

预处理出F[i][j]表示第i行，以j为起点连续的1的数量
首先选定一列作为全1矩阵的最左端，然后将预处理出连续1的数量看成一个直方图，然后用单调栈求出此时的最大面积，可以参考
[post cid=”74” /]

代码

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

int n,m,a[1005][1005],h[1005],ans;
bool t[1005][1005];
char s[3];
struct node{
    int h,w;
};
void solve(){
    stack <node> st;
    int tmp=h[1];
    st.push({h[1],1});
    for (int i=2;i<=n+1;++i){
        if (h[i]>st.top().h) st.push({h[i],1});
        else {
            int tw=0;
            while (!st.empty() && st.top().h>h[i]){
                tw+=st.top().w;
                tmp=max(tmp,tw*st.top().h);
                st.pop();
            }
            st.push({h[i],tw+1});
        }
    }
    ans=max(ans,tmp);
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=m;++j){
            scanf("%s",s+1);
            t[i][j]=s[1]=='F';
        }
    }
    for (int i=1;i<=n;++i){
        for (int j=m;j>=1;--j){
            if (t[i][j]) a[i][j]=a[i][j+1]+1;
            else a[i][j]=0;
        }
    }
    for (int i=1;i<=m;++i){
        for (int j=1;j<=n;++j) h[j]=a[j][i];
        solve();
    }
    cout<<3*ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/99/