推荐再写一下 直方图中最大的矩形
#include <iostream>
using namespace std;
const int N = 3010;
int g[N][N],h[N][N]; // g数组存储当前方格是否被破坏,h数组存储每一列中最大的方格数
int n,m,p;
int l[N],r[N];
int stk[N],top;
int work(int h[]) {
// 将左右边界都预处理为-1,防止中间的长度有0的
h[0] = h[m+1] = -1;
// 处理左边界
top = 0;
stk [++ top] = 0; // 入栈
for(int i = 1;i <= m;i++) {
// 如果栈顶元素较大,出栈
while(h[stk[top]] >= h[i]) top --;
l[i] = stk[top];// 此时栈中的数都是小于准备入栈的的这一列的值
stk[++top] = i;// 然后将当前的入栈
}
// 处理右边界
top = 0;
stk [++ top] = m + 1; // 入栈
for(int i = m;i;i--) {
while(h[stk[top]] >= h[i]) top --;
r[i] = stk[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(){
scanf("%d%d%d",&n,&m,&p);
while(p--) {
int x,y;
scanf ("%d%d",&x,&y);
g[x][y] = 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;
}
}
}
int res = 0;
// 开始遍历下界 并且找出最大的那个下界的矩形值
for(int i = 1;i <= n;i++) {
res = max(res,work(h[i]));
}
printf("%d\n",res);
return 0;
}