单调栈

　单调栈计算次大全一矩阵面积 #include<bits/stdc++.h> using namespace std; const int maxn=1000+5; int a[maxn][maxn]; typedef long long ll; typedef pair<int,int>pii; int maxv,ans; void cal(int x,int y) {

　 int res=x*y;

　 if(res>maxv)

　 {

　 ans=maxv;

　 maxv=res;

　 }

　 else if(res>ans)

　 {

　 ans=res;

　 } } void solve(int x,int y) {

　 cal(x,y);

　 cal(x-1,y);

　 cal(x,y-1); } int main() {

　 int n,m;

　 scanf("%d%d",&n,&m);

　 for(int i=1;i<=n;i++)

　 {

　 for(int j=1;j<=m;j++)

　 {

　 scanf("%1d",&a[i][j]);

　 a[i][j]+=a[i][j]==0?0:a[i-1][j];

　 }

　 }

　 for(int i=1;i<=n;i++)

　 {

　 stack<pii>s;

　 for(int j=1;j<=m;j++)

　 {

　int w=0,h;

　 while(!s.empty()&&s.top().second>=a[i][j])

　 {

　 h=s.top().second;

　 w+=s.top().first;

　 solve(w,h);

　 s.pop();

　 }

　 s.push(pii(w+1,a[i][j]));

　 }

　 int t=0;

　 while(!s.empty())

　 {

　 int w=s.top().first+t;

　 int h=s.top().second;

　 solve(w,h);

　 t+=s.top().first;

　 s.pop();

　 }

　 }

　 cout<<ans; }