题目描述
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入输出格式
输入格式：第一行为3个整数，分别表示a,b,n的值
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出格式：仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。
输入输出样例
输入样例#1：
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
输出样例#1：
1
说明
问题规模
（1）矩阵中的所有数都不超过1,000,000,000
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
Solution：
本题单调队列（当然也可以倍增）。
如果是一维的情况，就是经典的滑动窗口求极值的问题了。
考虑二维的情况，我们在每行都跑下单调队列，处理出$(i,j)$往左$n$个位置的极值。
再在处理出的$(i,j)$的行极值上，以每列的情况跑下单调队列，就能处理出$(i,j)$为右下角所在的$n*n$矩形内的极值了。
代码：
/*Code by 520 -- 9.19*/ #include<bits/stdc++.h> #define il inline #define ll long long #define RE register #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--) using namespace std; const int N=1005; int a,b,n,l1,r1,l2,r2,mp[N][N],x[N][N][2],y[N][N][2],q[N][2],ans=0x7fffffff; int gi(){ int a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-') x=getchar(); if(x=='-') x=getchar(),f=1; while(x>='0'&&x<='9') a=(a<<3)+(a<<1)+(x^48),x=getchar(); return f?-a:a; } int main(){ a=gi(),b=gi(),n=gi(); For(i,1,a) For(j,1,b) mp[i][j]=gi(); For(i,1,a) { l1=1,r1=0,l2=1,r2=0; For(j,1,b) { while(l1<=r1&&mp[i][q[r1][0]]>=mp[i][j]) r1--; q[++r1][0]=j; while(l2<=r2&&mp[i][q[r2][1]]<=mp[i][j]) r2--; q[++r2][1]=j; while(q[l1][0]<=j-n) l1++; while(q[l2][1]<=j-n) l2++; if(j>=n) x[i][j][0]=mp[i][q[l1][0]],x[i][j][1]=mp[i][q[l2][1]]; } } For(j,n,b) { l1=1,r1=0,l2=1,r2=0; For(i,1,a) { while(l1<=r1&&x[q[r1][0]][j][0]>=x[i][j][0]) r1--; q[++r1][0]=i; while(l2<=r2&&x[q[r2][1]][j][1]<=x[i][j][1]) r2--; q[++r2][1]=i; while(q[l1][0]<=i-n) l1++; while(q[l2][1]<=i-n) l2++; if(i>=n) ans=min(ans,x[q[l2][1]][j][1]-x[q[l1][0]][j][0]); } } cout<<ans; return 0; }