「一本通 5.5 练习 3」理想的正方形

形式化题目

给定 $a \times b$ 的非负整数矩阵，取出其中所有边长为 $n$ 的连续正方形子矩阵（ $n \le a$ 且 $n \le b$ ）。每个正方形用「内部最大值 − 内部最小值」衡量好坏，求这些差值的最小值。

样例矩阵（ $a=5,\ b=4,\ n=2$ ）与最优正方形如下，加粗的 6 个数是两个差值为 $1$ 的正方形（左上角 $(2,2)$ 与 $(3,2)$ ）的并集，因此输出 $1$ ：

行\列	c0	c1	c2	c3
r0	1	2	5	6
r1	0	17	16	0
r2	16	17	2	1
r3	2	10	2	1
r4	1	2	2	2

读表时可以对照任意一个 $2 \times 2$ 区块自己算一遍差值：加粗的两块都是 $\max = 2,\ \min = 1$ ，差为 $1$ ；换到别的位置，差值最小的也有 $8$ ，这就是答案 $1$ 的来源。

正解

思路

1. 朴素做法与瓶颈

最直接的做法：枚举 $(a-n+1)(b-n+1)$ 个正方形，每个就地扫一遍 $n^2$ 个格子求最大值和最小值，记录差的最小值。

代价是 $O(abn^2)$ ：正方形最多约 $10^6$ 个，每个 $n^2$ 最多 $10^4$ ，最坏约 $10^{10}$ 次读数，必然超时。重复的根源在于相邻正方形大量重叠——左右相邻的两个正方形共享 $n(n-1)$ 个格子，同一行里滑过的 $n$ 个窗口都会把中间的格子重数一遍。所以要消除的正是 $n^2$ 这个因子：让每个位置的窗口最值只被均摊 $O(1)$ 地算出来。

2. 一维基础：固定长度窗口的最值

窗口长度固定为 $n$ 、左右端点随枚举单调右移，这正是滑动窗口最值的标准形状，用单调队列可以在均摊 $O(1)$ 内拿到每个窗口的答案：

队列里存下标，队列内对应的值保持单调，于是队首就是当前窗口的最值；
新元素入队前，把队尾所有被它"支配"的下标弹掉（求最小值时即队尾 $\ge$ 新值；等于时也留新去旧，因为新下标更靠右、更晚过期，能让过期判断更及时），被弹的下标从此不可能再成为任何窗口的最值；
队首滑出窗口（下标 $< i-n+1$ ）时弹出，保证队首始终有效；
每个下标入队一次、出队至多一次，窗口右移一步产出一个答案，总代价 $O(n)$ 。

3. 二维分解：先横向、再纵向

单个正方形的最小值可以按维度拆开：

\text{方格min}(i,j) = \min_{r=i}^{i+n-1} \Big( \min_{c=j}^{j+n-1} a_{r,c} \Big) = \min_{r=i}^{i+n-1} \text{row\_min}[r][j],

内层是"第 $r$ 行上长度 $n$ 、横向滑动"的窗口最小值，外层又是一次"长度 $n$ 、纵向滑动"的窗口最小值。求最大值完全对称，只要把 $\min$ 换成 $\max$ 。于是两遍一维滑窗即可覆盖整个正方形，中间没有任何近似：row_min[r][j] 覆盖第 $r$ 行的 $[j, j+n)$ ，再对 $r \in [i, i+n)$ 取 min，扫过的格子恰好是正方形 $(i,j)$ 的全部 $n^2$ 个格子。

整条流水线长这样：

text

1
2
3
4
5
6
7a x b 矩阵（逐行读入，行窗口表就地生成，不整体保存）
|- 每行做长度 n 的窗口 min  ->  row_min 表（a 行 x (b-n+1) 列）
|- 每行做长度 n 的窗口 max  ->  row_max 表（同尺寸）
   `- 对两张表的同一列再做长度 n 的窗口
      |- 列窗口 min  ->  每个正方形的最小值
      |- 列窗口 max  ->  每个正方形的最大值
         `- ans = min(所有正方形的 最大值 - 最小值)

行列完全对称：min 走两遍 min，max 走两遍 max，互不交叉；四次窗口调用共用同一个 window_best 函数，只是 pick 参数不同。

4. 样例演算

把 12 个正方形的差值全部列出（行号 $i$ 、列号 $j$ 是正方形左上角，每格 = 该正方形的 $\max - \min$ ）：

i\j	j0	j1	j2
i0	17	15	16
i1	17	15	16
i2	15	15	1
i3	9	8	1

表中最小值是 $1$ ，出现在左上角 $(2,2)$ 和 $(3,2)$ 两个位置，与样例输出一致。用两遍滑窗核对其中一列：把 row_min 的窗口列 $j=2$ 抽出来是 $[5, 0, 1, 1, 2]$ ，再做纵向长度 2 的窗口最小值得 $[0, 0, 1, 1]$ ；row_max 的窗口列 $j=2$ 是 $[6, 16, 2, 2, 2]$ ，纵向窗口最大值得 $[16, 16, 2, 2]$ ，逐项作差得 $[16, 16, 1, 1]$ ，正是差值表的 j2 列。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 21:16
# update_at: 2026-09-30 21:35

import sys
from collections import deque
from collections.abc import Callable


def window_best(seq: list[int], k: int, pick: Callable[[int, int], int]) -> list[int]:
    """长度 k 的滑动窗口逐个求最值：pick 传 min 或 max，产出 len(seq)-k+1 个结果。"""
    dq: deque[int] = deque()  # 存下标，对应值按 pick 单调，队首下标就是窗口最值
    best: list[int] = []
    for i, value in enumerate(seq):
        while dq and pick(seq[dq[-1]], value) == value:
            dq.pop()  # 新值更优（或相等且更靠右），旧队尾永远轮不上
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()  # 队首已滑出窗口
        if i >= k - 1:
            best.append(seq[dq[0]])
    return best


def solve() -> None:
    header = iter(map(int, sys.stdin.buffer.readline().split()))
    row_count, col_count, side = next(header), next(header), next(header)  # a, b, n

    # 横向：逐行读入立即压成两张行窗口表，原矩阵不整体驻留内存
    row_min: list[list[int]] = []
    row_max: list[list[int]] = []
    for _ in range(row_count):
        row = list(map(int, sys.stdin.buffer.readline().split()))
        row_min.append(window_best(row, side, min))
        row_max.append(window_best(row, side, max))

    # 纵向：行窗口表第 c 列再滑一次；min/max 各自两遍复合正是 n×n 方格的最值。
    # 方格差值上界 1e9，先给大数作初始答案再逐格收紧。
    ans = 10**18
    for c in range(col_count - side + 1):
        col_min = window_best([row_min[r][c] for r in range(row_count)], side, min)
        col_max = window_best([row_max[r][c] for r in range(row_count)], side, max)
        for square_min, square_max in zip(col_min, col_max):
            ans = min(ans, square_max - square_min)

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:13
 * update_at: 2026-10-05 12:13
 */
// main.cpp：单调队列做二维滑动窗口最值，求最小的「n×n 方格最大值 − 最小值」。
// 先对每行横向滑窗得到行窗口最值表，再对行窗口表的每列纵向滑窗，
// 两次 min 复合还是方格最小值，两次 max 复合还是方格最大值。
#include <cstdio>

typedef long long ll;

const int MAXN = 1005; // 矩阵长宽上限

ll a, b, n;              // a 行、b 列、正方形边长 n
int line[MAXN];          // 当前读入的一行原始数据，压完即弃，不保存整个矩阵
int row_min[MAXN][MAXN]; // row_min[r][c]：第 r 行 [c, c+n) 的最小值（行窗口表）
int row_max[MAXN][MAXN]; // row_max[r][c]：第 r 行 [c, c+n) 的最大值（行窗口表）
ll q[MAXN];              // 单调队列，存下标，对应值按 mode 保持单调
int col_min[MAXN];       // 当前这一列纵向滑窗得到的方格最小值
int col_max[MAXN];       // 当前这一列纵向滑窗得到的方格最大值
int tmp[MAXN];           // 纵向滑窗时暂存的一列

// 对 src[1..len] 做长度 k 的滑动窗口最值，结果依次写入 dst[1..len-k+1]。
// mode = 0 求最小值，mode = 1 求最大值。
void window_best(int *src, ll len, ll k, int mode, int *dst) {
    ll head = 1; // 队首指针
    ll tail = 0; // 队尾指针，head > tail 表示队空
    ll cnt = 0;  // 已产出的窗口个数
    for (ll i = 1; i <= len; i++) {
        while (head <= tail) {
            ll back = q[tail];
            // 队尾被新值支配：求 min 时队尾 >= 新值（取等也弹，新下标更靠右、更晚过期）
            bool remove = (mode == 0 ? src[back] >= src[i] : src[back] <= src[i]);
            if (!remove) break;
            tail--;
        }
        q[++tail] = i;
        if (q[head] <= i - k) head++; // 队首下标已滑出窗口
        if (i >= k) dst[++cnt] = src[q[head]];
    }
}

int main() {
    scanf("%lld%lld%lld", &a, &b, &n);
    for (ll r = 1; r <= a; r++) {
        for (ll c = 1; c <= b; c++) {
            scanf("%d", &line[c]);
        }
        window_best(line, b, n, 0, row_min[r]);
        window_best(line, b, n, 1, row_max[r]);
    }

    ll width = b - n + 1;   // 每行可以放下的正方形个数
    ll height = a - n + 1;  // 每列可以放下的正方形个数
    ll ans = 2000000000LL;  // 差值上界 1e9，先放一个更大的数再逐格收紧
    for (ll c = 1; c <= width; c++) {
        for (ll r = 1; r <= a; r++) tmp[r] = row_min[r][c];
        window_best(tmp, a, n, 0, col_min);
        for (ll r = 1; r <= a; r++) tmp[r] = row_max[r][c];
        window_best(tmp, a, n, 1, col_max);
        for (ll i = 1; i <= height; i++) {
            ll diff = col_max[i] - col_min[i]; // 左上角为 (i, c) 的 n×n 方格差值
            if (diff < ans) ans = diff;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

复杂度

时间复杂度： $O(ab)$ 。横向每个元素入队一次、出队至多一次，共 $O(ab)$ ；纵向处理 $b-n+1$ 个窗口列、每列 $a$ 个元素，也是 $O(ab)$ ；收尾求差 $(a-n+1)(b-n+1)$ 次。相比朴素 $O(abn^2)$ 最坏约 $10^{10}$ ，消掉了 $n^2$ 因子。
空间复杂度： $O(a(b-n+1))$ ，只保存两张行窗口表。读入按行进行，一行压完即丢弃原行、不保存整个 $1000 \times 1000$ 矩阵；实测 10 组真实数据峰值内存 $\le 67$ MB，低于 128 MB 限制（一次性读入全部输入并保存整矩阵的写法实测峰值约 137 MB，会超限）。

总结

相邻正方形高度重叠，逐个重扫是无效劳动；把问题转成"固定长度窗口的最值"，单调队列均摊 $O(1)$ 消掉 $n^2$ 因子。
二维窗口最值靠 min/max 的复合性质分解成两次一维：先每行横向滑窗得到行窗口表，再对行窗口表的每列纵向滑窗，结果恰好是每个正方形的最值。
min 走两遍 min、max 走两遍 max，互不交叉，所以四次窗口调用复用同一个函数，代码只有一个过程函数。
边界自动成立： $n=1$ 时方格差恒为 $0$ ； $n=b$ （或 $n=a$ ）时行窗口表只剩 1 列（1 行）；方格数恒 $\ge 1$ ，初始大数哨兵必被覆盖。
内存要点：行窗口表就地生成、原矩阵不驻留，峰值从约 137 MB 降到 67 MB，才稳稳落在 128 MB 限制之内。