题目
Description
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
Input
第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
100%的数据2<=a,b<=1000,n<=a,n<=b,n<=1000
Output
仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。
Sample Input
5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2
Sample Output
1
思路
根据题目样例的意思；
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
我们可以求出每横排 n 个宽度的最大值；
也就是这样
2 5 6
17 17 16
17 17 2
10 10 2
2 2 2
然后再求竖排 n 个宽度的最大值；
也就是
17 17 16
17 17 16
17 17 2
10 10 2
这样每个点就代表一个n*n 的正方形；
然后用同样的方法求一波每个正方形代表的最小值；
最后，根据题意求出
n*n正方形区域中的最大整数和最小整数的差值 的最小值
也就是把上面每个点的值相减，然后求一波 min 就ok了；
代码
#include<bits/stdc++.h> #define re register typedef long long ll; using namespace std; inline ll read() { ll a=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') {a=a*10+c-'0'; c=getchar();} return a*f; } ll a,b,n; ll map1[1010][1010]; ll val[1010]; ll mx[1010][1010],mn[1010][1010]; ll ans[1010][1010],sum[1010][1010]; ll q[1010]; int main() { a=read(); b=read(); n=read(); for(re ll i=1;i<=a;i++) for(re ll j=1;j<=b;j++) map1[i][j]=read();//读入 ll tot=0; for(re ll k=1;k<=a;k++)//k 代表每一行 { ll head=1,tail=0; tot=0; for(re ll i=1;i<=b;i++)// i 是每一列 { while(head<=tail&&i-q[head]+1>n)//如果队列长度大于n 那么踢队头 head++; while(head<=tail&&map1[k][i]>map1[k][q[tail]])//严格单调下降 tail--; q[++tail]=i; if(i>=n) mx[k][++tot]=map1[k][q[head]];//单调队列板子，横排求一波最大值； //k 代表第几横排 ，tot 是第几个 n 宽度的max } } //同上，横排求一波最小值； ll cnt=0; for(re ll k=1;k<=a;k++) { ll head=1,tail=0; cnt=0; for(re ll i=1;i<=b;i++) { while(head<=tail&&i-q[head]+1>n)//如果队列长度大于n 那么踢队头 head++; while(head<=tail&&map1[k][i]<map1[k][q[tail]]) tail--; q[++tail]=i; if(i>=n) mn[k][++cnt]=map1[k][q[head]]; //k 代表第几横排 ，tot 是第几个 n 宽度的min } } ll s=0; for(re ll t=1;t<=tot;t++)//横排的max 个数 { s=0; for(re ll k=1;k<=a;k++) val[k]=mx[k][t];//将每一竖排的之前求出的max 值记下； ll head=1,tail=0; for(re ll i=1;i<=a;i++) { while(head<=tail&&i-q[head]+1>n)//如果队列长度大于n 那么踢队头 head++; while(head<=tail&&val[i]>val[q[tail]])//单调队列板子，竖排求一波最大值； tail--; q[++tail]=i; if(i>=n) ans[t][++s]=val[q[head]]; //t 代表第几横排 ，s 是竖排第几个 n 宽度的max } } memset(sum,127/3,sizeof(sum)); ll ss=0; //同上 ，求一波最小值； for(re ll t=1;t<=cnt;t++) { ss=0; for(re ll k=1;k<=a;k++) val[k]=mn[k][t]; ll head=1,tail=0; for(re ll i=1;i<=a;i++) { while(head<=tail&&i-q[head]+1>n)//如果队列长度大于n 那么踢队头 head++; while(head<=tail&&val[i]<val[q[tail]]) tail--; q[++tail]=i; if(i>=n) sum[t][++ss]=val[q[head]]; //t 代表第几横排 ，s 是竖排第几个 n 宽度的min } } ll answer=1<<30; for(re ll i=1;i<=tot;i++) for(re ll j=1;j<=s;j++)//枚举每个横排长度为 n 的 个数 和竖排的长度为 n 的个数 answer=min(answer,ans[i][j]-sum[i][j]);//每个n*n区域的max与min 之差 求最小值 printf("%lld ",answer); }