Description：

有一个 $a\times b$ 的整数组成的矩阵，现请你从中找出一个 $n\times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

$1\le a,b \le 1000$ $1\le n \le100$

Solution：

先对每行分别用单调队列像滑动窗口一样求出一个 $rmin,rmax$ ，表示从某个位置开始长为 $n$ 的区间内最大 $/$ 最小值，然后再对这两个数组的列做滑动窗口，就得到了从某个位置开始大小为 $n$ 的正方形的区间内最大 $/$ 最小值。然后枚举这个正方形就可以求最值了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int a,b,n;

#define MAXN 1010

int p[MAXN][MAXN];

int rmax[MAXN][MAXN],rmin[MAXN][MAXN],cmax[MAXN][MAXN],cmin[MAXN][MAXN];

int main()

{

	scanf("%d%d%d",&a,&b,&n);

	for(int i = 1;i <= a;++i)

		for(int j = 1;j <= b;++j)

			scanf("%d",&p[i][j]);

	for(int i = 1;i <= a;++i)

	{

		deque<int> q;

		for(int j = b;j >= b - n + 1;--j)

		{

			while(!q.empty() && p[i][j] >= p[i][q.front()])q.pop_front();

			q.push_front(j);

		}

		rmax[i][b - n + 1] = p[i][q.back()];

		for(int j = b - n;j >= 1;--j)

		{

			while(!q.empty() && p[i][j] >= p[i][q.front()])q.pop_front();

			q.push_front(j);

			if(q.back() - j + 1 > n)q.pop_back();

			rmax[i][j] = p[i][q.back()];

		}

		q.clear();

		for(int j = b;j >= b - n + 1;--j)

		{

			while(!q.empty() && p[i][j] <= p[i][q.front()])q.pop_front();

			q.push_front(j);

		}

		rmin[i][b - n + 1] = p[i][q.back()];

		for(int j = b - n;j >= 1;--j)

		{

			while(!q.empty() && p[i][j] <= p[i][q.front()])q.pop_front();

			q.push_front(j);

			if(q.back() - j + 1 > n)q.pop_back();

			rmin[i][j] = p[i][q.back()];

		}

	}

	for(int i = 1;i <= b - n + 1;++i)

	{

		deque<int> q;

		for(int j = a;j >= a - n + 1;--j)

		{

			while(!q.empty() && rmax[j][i] >= rmax[q.front()][i])q.pop_front();

			q.push_front(j);

		}

		cmax[a - n + 1][i] = rmax[q.back()][i];

		for(int j = a - n;j >= 1;--j)

		{

			while(!q.empty() && rmax[j][i] >= rmax[q.front()][i])q.pop_front();

			q.push_front(j);

			if(q.back() - j + 1 > n)q.pop_back();

			cmax[j][i] = rmax[q.back()][i];

		}

		q.clear();

		for(int j = a;j >= a - n + 1;--j)

		{

			while(!q.empty() && rmin[j][i] <= rmin[q.front()][i])q.pop_front();

			q.push_front(j);

		}

		cmin[a - n + 1][i] = rmin[q.back()][i];

		for(int j = a - n;j >= 1;--j)

		{

			while(!q.empty() && rmin[j][i] <= rmin[q.front()][i])q.pop_front();

			q.push_front(j);

			if(q.back() - j + 1 > n)q.pop_back();

			cmin[j][i] = rmin[q.back()][i];

		}

	}

	int ans = 0x7fffffff;

	for(int i = 1;i <= a - n + 1;++i)

	{

		for(int j = 1;j <= b - n + 1;++j)

		{

			ans = min(ans,cmax[i][j] - cmin[i][j]);

		}

	}

	cout << ans << endl;

	return 0;

}