题意:t个样例, n,m 给一个 n*n 矩形,值为高,求最大子矩阵面积,要求子矩阵中高度差不超过m
题解:枚举左边界, 对每个左边界L,枚举右边界R,对左右边界[L,R],维护每行区间最大,最小值。
然后枚举下边界 i (1~n)。单调队列q1存最大值下标,要求q1下标对应值严格单调递减,q2存最小值下标,q2中下标对应
值严格单调递增,当队列非空且max[ q1[back] ] - min[ q2[back] ] > m ,就让 tmp = min(q1[back],q2[back]),并让相应小的下标
出队,tmp 表示从 tmp+1 到 i 是合法的高度。 每次 ans = max(ans, (R-L+1)*( i-tmp ) );求矩形面积最大值。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
int mp[505][505];
int q1[2000],q2[2000];
int num1[505],num2[505];
int tp1,bk1,tp2,bk2;
int main()
{
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&mp[i][j]);
}
}
int ans = 0;
for(int L = 1; L <= n ; L++){// 固定左端点
for(int i = 1 ;i <= n ; i++)num1[i]=-inf,num2[i]=inf;
for(int R = L; R <=n ; R++){//枚举右端点
// 求每一行 从L到 R 最大最小值
for(int u=1;u<=n;u++) num1[u] = max(num1[u],mp[u][R]), num2[u] = min(num2[u],mp[u][R]);
int tmp = 0;
tp1 = tp2 = bk1 = bk2 = 1000;
for(int i=1; i<=n;i++){//枚举下边界
while(tp1 != bk1 && num1[i] >= num1[q1[bk1]]) bk1--;//q1 单调递减
while(tp2 != bk2 && num2[i] <= num2[q2[bk2]]) bk2--;//q2 单调递增
q1[++bk1] = i;
q2[++bk2] = i;
while(tp1!=bk1 && tp2!=bk2 && num1[q1[tp1+1]] - num2[q2[tp2+1]] > m){
if(q1[tp1+1] > q2[tp2+1]){
tmp = q2[tp2+1];
tp2++;
}else{
tmp = q1[tp1+1];
tp1++;
}
}
ans = max(ans,(R-L+1)*(i-tmp));
}
}
}
printf("%d\n",ans);
}
return 0;
}
/*
1
5 4
1 2 3 4 5
5 4 3 2 1
9 9 9 9 5
9 9 7 8 7
9 9 11 12 9
*/