AcWing 1091. 理想的正方形

题目传送门

一维滑动窗口模板题

一、解题思路

二维滑动窗口模板题

①和②的步骤都是用单调队列来进行优化
核心思路

一维单调队列求解区间的最值

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 + 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 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;
        //因为第i个元素也可能包含，所以最后再处理
        b[i] = a[q[hh]];
    }
}

步骤1.枚举每行所有长度为k的区间的最值，保存在区间的右端点中

//分别找到每一行的每个[j - n - 1,j]区间的最小值和最大值
    for(int i = 1;i <= n;++i){
        get_min(w[i],row_min[i],m);
        get_max(w[i],row_max[i],m);
    }

步骤2.枚举长度为k的同一列的左端点，得到最值，保存在区间的下端点中

//接着找到每列的最大值和最小值（直接从第n列开始,即表示第一个n * n的矩阵的每行内的最大元素）
    for(int j = k;j <= m;++j){ 
        //枚举列，因为第一个区间内的最大值或者最小值开始是存放在下标为n

        //枚举行，计算当前这一列中所有横向区间的最值复制给ans
        for(int i = 1;i <= n;++i) ans[i] = row_min[i][j];
        get_min(ans,col_min,n);   //最多有n行


        for(int i = 1;i <= n;++i) ans[i] = row_max[i][j];
        get_max(ans,col_max,n);
}

步骤3.计算这一列的所有最大值和最小值的差值，更新结果

for(int i = k;i <= n;++i){
    res = min(res,col_max[i] - col_min[i]);
}

二、完整代码

#include 

using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;

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

void get_min(int a[], int b[], int tot) {
    int hh = 0, tt = 0;
    for (int i = 1; i <= tot; i++) {
        if (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 = 0;
    for (int i = 1; i <= tot; i++) {
        if (q[hh] <= i - k) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        //记录最新的队头元素值
        b[i] = a[q[hh]];
    }
}


int main() {
    cin >> n >> m >> k;
    //读入
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> w[i][j];

    //计算每一行的最小值和最大值,分别保存到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 res = INF;
    int a[N], b[N], c[N];
    //遍历每一个有意义的列
    for (int i = k; i <= m; i++) {
        //将此列每一行的数据拷贝到a数组中，可以再次调用二维模板进行最小值计算
        for (int j = 1; j <= n; j++) a[j] = row_min[j][i];
        get_min(a, b, n);
        //将此列每一行的数据拷贝到a数组中，可以再次调用二维模板进行最大值计算
        for (int j = 1; j <= n; j++) a[j] = row_max[j][i];
        get_max(a, c, n);
        //找出min(区域最大值-区域最小值)
        for (int j = k; j <= n; j++) res = min(res, c[j] - b[j]);
    }
    //输出
    printf("%d\n", res);
    return 0;
}