题目：https://ac.nowcoder.com/acm/contest/883/F
题意：求一个矩阵最大面积，这个矩阵的要求是矩阵内最小值与最大值差值<=m
思路：首先我们仔细观察范围，我们就知道可以n^3,前面这题我（看付队博客）讲过求一个最大的什么矩阵就是分两种情况，
第一种：枚举上下边界，转化为一维，复杂度n^3
第二种：枚举下边界，转化为高楼问题，复杂度n^2
这里显然复杂度可以n^3，我们就想一下三场循环，这题实际上就是找到矩阵内的最大值最小值
第一层肯定是枚举上边界
第二层我们要边枚举下边界边求当前列的最大最小值
第三层 这里其实也就是转化为了一个一维的题，求一个序列内，每个有一个最大最小值，任意两点差值不超过m，然后问最大连续长度是多少
这个其实很简单，我们用两个单调队列分别记录最大最小值，然后尺取过去即可，这里必须手动模拟队列，不然会超时。（亲测）
附：我们第一层枚举上边界，第二层枚举下边界是有特殊原因的，这样方便O(n)求出所有最大值
#include<bits/stdc++.h>
#define maxn 505
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,m;
ll mp[maxn][maxn];
ll mx[maxn],mn[maxn];
ll qn[maxn],qx[maxn];
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld",&n,&m);
ll ans=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%lld",&mp[i][j]);
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
mx[j]=-mod;
mn[j]=mod;
}
for(int j=i;j<=n;j++){
for(int k=;k<=n;k++){
mx[k]=max(mx[k],mp[j][k]);
mn[k]=min(mn[k],mp[j][k]);
}
ll l=,r=,f1=,f2=,b1=,b2=;
while(r<=n){
while(f1<=b1&&mx[r]>=mx[qx[b1]]) b1--;
qx[++b1]=r;
while(f2<=b2&&mn[r]<=mn[qn[b2]]) b2--;
qn[++b2]=r;
if(mx[qx[f1]]-mn[qn[f2]]<=m){
ans=max((r-l+)*(j-i+),ans);
r++;
continue;
}
ans=max((r-l)*(j-i+),ans);
while(l<=r&&mx[qx[f1]]-mn[qn[f2]]>m){
l++;
while(f1<=b1&&qx[f1]<l) f1++;
while(f2<=b2&&qn[f2]<l) f2++;
}
r++;
}
}
}
printf("%lld\n",ans);
}
return ;
}