【题目-理想的正方形】 二维单调队列

理想的正方形 （二维单调队列）

题目

• acwing.1091 理想的正方形

题解

• 题目很好做，主要学习一下二维单调队列的写法
• 首先将每行各窗口内最值用单调队列维护出来，保存在rmax中
• 接着对rmax各列，将每列最值用单调队列维护出来，保存在cmax中，最后cmax中存的就是行和列窗口乘积范围的二维区间最值
• 最小值同理

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 2e3 + 5;

int n, m, z;
int w[N][N];
int res = 0x3f3f3f3f;
int q[N], h, t;

int rmax[N][N], rmin[N][N];
int cmax[N][N], cmin[N][N];


void get_max(int i){
    h = 0, t = -1;
    for(int j = 1; j < z; ++ j) {
        while(h <= t && w[i][j] >= w[i][q[t]]) t--;
        q[++ t] = j;
    }
    for(int j = z; j <= m; ++ j) {
        while(h <= t && q[h] <= j - z) h ++;
        while(h <= t && w[i][j] >= w[i][q[t]]) t --;
        q[++ t] = j;
        rmax[i][j] = w[i][q[h]];
    }
}

void get_min(int i) {
    h = 0, t = -1;
    for(int j = 1; j < z; ++ j) {
        while(h <= t && w[i][j] <= w[i][q[t]]) t --;
        q[++ t] = j;
    }
    for(int j = z; j <= m; ++ j) {
        while(h <= t && q[h] <= j - z) h ++;
        while(h <= t && w[i][j] <= w[i][q[t]]) t --;
        q[++ t] = j;
        rmin[i][j] = w[i][q[h]];
    }
}

void get_max_c(int j) {
    h = 0, t = -1;
    for(int i = 1; i < z; ++ i) {
        while(h <= t && rmax[i][j] >= rmax[q[t]][j]) t --;
        q[++ t] = i;
    }
    for(int i = z; i <= n; ++ i) {
        while(h <= t && q[h] <= i - z) h ++;
        while(h <= t && rmax[i][j] >= rmax[q[t]][j]) t --;
        q[++ t] = i;
        cmax[i][j] = rmax[q[h]][j];
    }
}

void get_min_c(int j) {
    h = 0, t = -1;
    for(int i = 0; i < z; ++ i){
        while(h <= t && rmin[i][j] <= rmin[q[t]][j]) t --;
        q[++ t] = i;
    }
    for(int i = z; i <= n; ++ i) {
        while(h <= t && q[h] <= i - z) h ++;
        while(h <= t && rmin[i][j] <= rmin[q[t]][j]) t --;
        q[++ t] = i;
        cmin[i][j] = rmin[q[h]][j];
    }
}

int main() {
    scanf("%d%d%d",&n, &m, &z);
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            scanf("%d",&w[i][j]);
    
    for(int i = 1; i <= n; ++ i) {
        get_max(i);
        get_min(i);
    }
    for(int j = z; j <= m; ++ j) {
        get_max_c(j);
        get_min_c(j);
    }
    int res = 0x3f3f3f3f;
    for(int i = z; i <= n; ++ i)
        for(int j = z; j <= m; ++ j)
            res = min(res, cmax[i][j] - cmin[i][j]);
    
    printf("%d\n",res);
    
    return 0;
}