矩形牛棚
单调栈:
解决问题:找出数组中每一个数左边比他小的第一个数a,保证每一个数入栈时,栈中有一个比这个数小的数(stk[0]=-0x3f3f3f3f)
操作:每一个数入栈时
1.若栈顶元素小于这个数,答案a是栈顶元素,这个数进行入栈
2.若栈顶元素大于等于这个数,依次对元素出栈直到栈顶元素小于这个数,此时栈顶元素是a
单调栈
stk[i]存放的是每一行元素的下标,进栈比较的是h[i]
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3010;
int n,m,p;
int h[N][N]; //表示点向上的最大有效高度(含该点)
int g[N][N];
int l[N],r[N]; //l[i]表示每一行纵坐标为i的点,左边第一个小于h[i]的点的纵坐标
int stk[N]; //r[i]表示每一行纵坐标为i的点,右边第一个小于h[i]的点的纵坐标
int top;
int work(int *h){
h[0]=-1; //初始化,保证每个数入栈,栈都有小于这个数的数存在
h[m+1]=-1;
int top=1;
stk[top]=0;
for(int i=1;i<=m;i++){
while(h[i]<=h[stk[top]]){
top--;
}
l[i]=stk[top];
top++;
stk[top]=i;
}
top=1;
stk[top]=m+1;
for(int i=m;i>=1;i--){
while(h[i]<=h[stk[top]]){
top--;
}
r[i]=stk[top];
top++;
stk[top]=i;
}
int res=0;
for(int i=1;i<=m;i++){
res=max(res,h[i]*(r[i]-l[i]-1));
}
return res;
}
int main(){
cin>>n>>m>>p;
while(p--){
int r,c;
cin>>r>>c;
g[r][c]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!g[i][j]){
h[i][j]=h[i-1][j]+1; //从上往下递推求h数组
}
}
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,work(h[i])); //遍历下边界1-n
}
printf("%d\n",res);
}