理想的正方形

原题链接

题目描述

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

---

思路 二维最值+单队列优化

根据题意，我们需要找到二维数组内的最小值和最大值，如果每次朴素求最值的话，时间复杂度为 \(O(n^2)\)。是不能接受的，于是考虑单调队列优化。

可以发现，先求横向的最值，然后纵向就是由横向的最值求出，时间复杂度可以降至 \(O(n)\)。

定义两个数组，分别为 \(row\_ min[i][j],row\_ max[i][j]\)，代表第 \(i\) 行，右边界为 \(j\)，区间长度为 \(k\) 的区间最小（大）值。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m, k;
int row_min[N][N], row_max[N][N];
int w[N][N];
int q[N];

/*
 * function of get_min & get_max:
 * a[] is the array of target;
 * b[] is the array of result;
 * tot is the length of array a[].
 */

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> w[i][j];

    // To get n rows of row_min & row_max.
    for (int i = 1; i <= n; i++) {
        get_min(w[i], row_min[i], m);
        get_max(w[i], row_max[i], m);
    }

    int a[N], b[N], c[N];
    // Array b is min of square, array c is max of square.

    int res = 1e9;
    // The begin of right boundary is k.
    for (int i = k; i <= m; i++) {
        // Get the min of square.
        for (int j = 1; j <= n; j++) a[j] = row_min[j][i];
        get_min(a, b, n);

        // Get the max of square.
        for (int j = 1; j <= n; j++) a[j] = row_max[j][i];
        get_max(a, c, n);

        // res = min(max - min);
        // Also, the begin of bottom boundary is k.
        for (int j = k; j <= n; j++) res = min(res, c[j] - b[j]);
    }

    cout << res << endl;

    return 0;
}