P2216 [HAOI2007] 理想的正方形

题目描述

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

输入格式

第一行为 $3$ 个整数，分别表示 $a,b,n$ 的值。

第二行至第 $a+1$ 行每行为 $b$ 个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
4
5
6
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$。

$20%$ 的数据 $2 \le a,b \le 100,n \le a,n \le b,n \le 10$。

$100%$ 的数据 $2 \le a,b \le 1000,n \le a,n \le b,n \le 100$。

题解

  • 求出一个正方形中的最大值 只需先求出每一行的最大值 再在这些最大值中求最大值
  • 相当于将一个二维问题转换为两个一维问题

错误想法

  • 为什么不能将二维矩形直接展开成一个一维长条？
  • 因为按照矩阵遍历的额方向 不能保证所有可能滑出区间的值都在队首 无法正确处理右上角出队的问题
  • 由此可知 一个单调队列只能处理一个维度上的情况 如果有多维需要一维一维地求

代码

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
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
#define MAXA 1010
int a, b, n;
int mt[MAXA][MAXA];
int rM[MAXA][MAXA], rm[MAXA][MAXA];
int mM[MAXA][MAXA], mm[MAXA][MAXA];
int qx[MAXA];
int h = 0, t = -1;

int main() {
    cin >> a >> b >> n;
    for(int i=1; i<=a; i++) {
        for(int j=1; j<=b; j++) {
            cin >> mt[i][j];
        }
    }
    // 求每行每个区间的最大值
    for(int i=1; i<=a; i++) {
        memset(qx, 0, sizeof qx);
        h = 0, t = -1;
        for(int j=1; j<=b; j++) {
            while(h<=t&& mt[i][qx[t]] < mt[i][j]) {
                t--;
            }
            qx[++t] = j;
            while(qx[h]+n<=j) h++;
            if(j>=n) mM[i][j-n+1] = mt[i][qx[h]];
        }
    }
    // 求某个方形中行最大值的最大值
    for(int j=1; j<=b-n+1; j++) {
        memset(qx, 0, sizeof qx);
        h = 0, t = -1;
        for(int i=1; i<=a; i++) {
            while(h<=t&& mM[qx[t]][j] < mM[i][j]) {
                t--;
            }
            qx[++t] = i;
            while(qx[h]+n<=i) h++;
            if(i>=n) rM[i-n+1][j] = mM[qx[h]][j];
        }
    }
    // 求每行每个区间最小值
    for(int i=1; i<=a; i++) {
        memset(qx, 0, sizeof qx);
        h = 0, t = -1;
        for(int j=1; j<=b; j++) {
            while(h<=t&& mt[i][qx[t]] > mt[i][j]) {
                t--;
            }
            qx[++t] = j;
            while(qx[h]+n<=j) h++;
            if(j>=n) mm[i][j-n+1] = mt[i][qx[h]];
        }
    }
    // 求某个方形中行最小值的最小值
    for(int j=1; j<=b-n+1; j++) {
        memset(qx, 0, sizeof qx);
        h = 0, t = -1;
        for(int i=1; i<=a; i++) {
            while(h<=t&& mm[qx[t]][j] > mm[i][j]) {
                t--;
            }
            qx[++t] = i;
            while(qx[h]+n<=i) h++;
            if(i>=n) rm[i-n+1][j] = mm[qx[h]][j];
        }
    }
    // 求每个格子对应的极差的最小值
    int ans = 1e9;
    for(int i=1; i<=a-n+1; i++) {
        for(int j=1; j<=b-n+1; j++) {
            ans = min(ans, rM[i][j] - rm[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}