好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

原题来自：HAOI 2007

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

输入格式

第一行为三个整数 $a, b, n$，分别表示矩阵的行数、列数和正方形的边长；

第二行至第 $a+1$ 行，每行 $b$ 个非负整数，表示矩阵中相应位置上的数。

输出格式

输出一个整数，为 $a \times b$ 矩阵中所有 $n \times n$ 正方形区域中的最大值与最小值的差值的最小值。

样例

样例输入

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

样例输出

1

样例解释

矩阵 $5\times 4$，正方形边长 $n=2$。

我们需要在所有 $2\times 2$ 子矩阵中，找出“最大值 − 最小值”最小的一个。

例如：

• 子矩阵 $\begin{bmatrix}1&2\\0&17\end{bmatrix}$，最大值 17，最小值 0，差 17；
• 子矩阵 $\begin{bmatrix}2&5\\17&16\end{bmatrix}$，最大值 17，最小值 2，差 15；
• ……
• 子矩阵 $\begin{bmatrix}2&1\\2&2\end{bmatrix}$（最后两行最后两列），最大值 2，最小值 1，差 1。

所有 $2\times 2$ 子矩阵的最小差值为 1。

数据范围

• 对于 $20\%$ 的数据，$2 \le a,b \le 100, n \le 10$；
• 对于 $100\%$ 的数据，$2 \le a,b \le 1000, n \le a, n \le b, n \le 100$，矩阵中的所有数不超过 $10^9$。

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

提示
此题为 二维滑动窗口最值 问题，可以用 单调队列 或 ST 表 解决，但由于 $n$ 固定且 $a,b$ 较大，一般采用两次单调队列。

思路：

1. 先对每一行，用长度为 $n$ 的滑动窗口求出该行每个窗口的最大值和最小值，分别存到两个数组 $row\_max[i][j]$ 和 $row\_min[i][j]$，表示第 $i$ 行从 $j$ 到 $j+n-1$ 的最大值和最小值（$j$ 从 $1$ 到 $b-n+1$）。
2. 再对列方向，用长度为 $n$ 的滑动窗口，对 $row\_max$ 和 $row\_min$ 进行列方向的最大最小值合并，得到每个 $n\times n$ 子矩阵的最大值和最小值。
3. 遍历所有 $n\times n$ 子矩阵，计算差值，取最小值。

具体步骤：

• 第一步（行处理）： 对每一行 $i$，用两个单调队列（一个递增、一个递减）求出长度为 $n$ 的滑动窗口的最大值和最小值，得到 $row\_max[i][j]$ 和 $row\_min[i][j]$，其中 $1 \le j \le b-n+1$。
• 第二步（列处理）： 对每一列 $j$（$1 \le j \le b-n+1$），用两个单调队列（一个递增、一个递减）在列方向对 $row\_max[1..a][j]$ 求长度为 $n$ 的窗口的最大值，得到 $col\_max[i][j]$（表示以 $(i,j)$ 为左上角的 $n\times n$ 子矩阵的最大值）；同理对 $row\_min$ 得到 $col\_min[i][j]$。
• 第三步（求答案）： 遍历 $i=1..a-n+1, j=1..b-n+1$，计算 $col\_max[i][j] - col\_min[i][j]$，取最小值。

复杂度：$O(a\times b)$，因为每个元素入队出队常数次。

注意：由于 $a,b \le 1000$，$n \le 100$，这种方法可以高效运行。