先横向、再纵向运行单调队列，在线性时间得到每个 n×n 方块的最大值和最小值。
OJ: luogu
题目 ID: P2216
难度:普及+/提高
标签:单调队列二维滑动窗口python
日期: 2026-07-16 18:25
题意
在矩阵所有固定边长正方形中，最小化内部最大值与最小值之差。
思路
先对每行做长度 side 的滑动最小值和最大值，得到所有横条结果；再对每个结果列做长度 side 的纵向滑动最值。第二遍得到的正好是每个正方形的整体最小值、最大值。
Python 知识
deque保存候选下标，横向和纵向各扫描一次。- 中间矩阵用
array("i")保存，百万级 32 位值内存稳定。 - 分开保存横向最小、最大结果，第二遍只访问所需列。
代码
python
import sys
from array import array
from collections import deque
input = sys.stdin.buffer.readline
rows, columns, side = map(int, input().split())
horizontal_min = []
horizontal_max = []
for _ in range(rows):
row = list(map(int, input().split()))
qmin, qmax = deque(), deque()
row_min, row_max = array("i"), array("i")
for j, value in enumerate(row):
while qmin and qmin[0] <= j - side:
qmin.popleft()
while qmin and row[qmin[-1]] >= value:
qmin.pop()
qmin.append(j)
while qmax and qmax[0] <= j - side:
qmax.popleft()
while qmax and row[qmax[-1]] <= value:
qmax.pop()
qmax.append(j)
if j >= side - 1:
row_min.append(row[qmin[0]])
row_max.append(row[qmax[0]])
horizontal_min.append(row_min)
horizontal_max.append(row_max)
answer = 1 << 60
for column in range(columns - side + 1):
qmin, qmax = deque(), deque()
for i in range(rows):
while qmin and qmin[0] <= i - side:
qmin.popleft()
while qmin and horizontal_min[qmin[-1]][column] >= horizontal_min[i][column]:
qmin.pop()
qmin.append(i)
while qmax and qmax[0] <= i - side:
qmax.popleft()
while qmax and horizontal_max[qmax[-1]][column] <= horizontal_max[i][column]:
qmax.pop()
qmax.append(i)
if i >= side - 1:
answer = min(answer, horizontal_max[qmax[0]][column]
- horizontal_min[qmin[0]][column])
print(answer)复杂度
时间复杂度
总结
二维固定窗口最值可以拆成两次一维单调队列。