原题链接

题目描述

给定一个n*m的矩w，在所有边长为k的子矩阵中，找到该子矩阵的最大值与最小值之差最小的矩阵，输出该差

分析

直接做不好做，分两步

1. 对每行做一遍滑动窗口，找到以i为右端点的长度为k的滑动窗口的最大值，将其存到对应位置上
2. 在1的前提下，对每列做一遍滑动窗口，则输出即为边长为k的子矩阵的最大值

最小值同理
然后枚举每个子矩阵，找到差值最小的即可

Code

#include <iostream>
#include <cstring>

constexpr int N = 1005;

int n, m, k;
int w[N][N], maxv[N][N], minv[N][N];
int q[N];

void get_min(int a[], int b[], int len) {
    int hh = 0, tt = -1;
    for (int i = 1; i <= len; i ++ ) {
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

void get_max(int a[], int b[], int len) {
    int hh = 0, tt = -1;
    for (int i = 1; i <= len; i ++ ) {
        if (hh <= tt && q[hh] < i - k + 1) hh ++ ;
        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;
        b[i] = a[q[hh]];
    }
}

int main() {
    std::cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ ) 
            std::cin >> w[i][j];
            
    for (int i = 1; i <= n; i ++ ) {
        get_min(w[i], minv[i], m);
        get_max(w[i], maxv[i], m);
    }
    
    int a[N], b[N], c[N], d[N];
    int res = 1e9;
    for (int i = k; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            a[j] = minv[j][i];
            b[j] = maxv[j][i];
        }
        get_min(a, c, n);
        get_max(b, d, n);

        for (int j = k; j <= n; j ++ ) res = std::min(res, d[j] - c[j]);
    }
    
    std::cout << res << '\n';
    return 0;
}