POJ - 3494 Largest Submatrix of All 1’s（单调栈求最大全1子矩阵）

链接：POJ - 3494 Largest Submatrix of All 1’s

题意

给出一个$n\times m$（$1\le n,m\le 2000$）的01矩阵，求最大的全为1的子矩阵，输出其面积（设矩阵单位长度为1）。

分析

对每一行进行考虑，均可以视为一个 柱状图，如上图，于是问题转化为为 求柱状图的最大矩形面积，这可以利用 单调栈 来处理，利用单调栈在$O(m)$时间内处理出 所有元素左边/右边第一个比其大/小的元素位置。

在利用单调栈处理之前，还需要求出 每个位置的 “柱高”，其实只需要 对每一列进行遍历，然后 从上到下依次编号 即可。

总的时间复杂度为$O(n?m)$。

代码

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int maxn=2e3+10;
int n,m,a[maxn][maxn];
int L[maxn],R[maxn];
void prework(int i)    //预处理第i行
{
    stack<int> st;for(int j=1;j<=m;j++){
    while(!st.empty()&&a[i][st.top()]>=a[i][j])st.pop();if(!st.empty())L[j]=st.top();     //a[i][j]左边第一个比其小的元素的下标elseL[j]=0;st.push(j);}while(!st.empty())st.pop();for(int j=m;j>=1;j--){
    while(!st.empty()&&a[i][st.top()]>=a[i][j])st.pop();if(!st.empty())R[j]=st.top();      //a[i][j]右边第一个比其小的元素的下标elseR[j]=m+1;st.push(j);}
}
int main()
{
    while(~scanf("%d %d",&n,&m)){
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);for(int j=1;j<=m;j++)     //得出每个位置的”柱高”{
    for(int i=1,cnt=0;i<=n;i++){
    if(a[i][j])a[i][j]=++cnt;elsecnt=0;}}int ans=0;for(int i=1;i<=n;i++){
    prework(i);for(int j=1;j<=m;j++)ans=max(ans,a[i][j]*(R[j]-L[j]-1));}printf("%d\n",ans);}return 0;
}