历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1091. 理想的正方形【二维滑动窗口模型】原题链接中等

作者：

一只野生彩色铅笔 , 2021-09-23 22:40:37 , 所有人可见 , 阅读 3432

41

7

最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一个 $a \times b$ 的矩阵 $w$，以及一个 正整数 $n$（其中 $w_{i,j}$ 为第 $i$ 行第 $j$ 列元素的价值）

求矩阵 $w$ 中，边长为 $n$，且元素 最小最大值的差值最小 的 子矩阵，输出该差值

分析

看到 区间最值 问题，第一反应是 预处理 st表，做一遍 二维RMQ

RMQ 本身是用于处理 多组询问 的，而本题则是要把所有 恒定边长 的 区间最值 找出来

介于只用维护 恒定边长，因此没有必要上 RMQ，但是 RMQ 的思想可以继承过来

考虑求一个二维的 最值问题，我们可以把它转化为一维的 最值问题：

图中 红色阴影 格为该行中的 最值元素，绿色背影色 格为整个矩阵的 最值元素

由常见公式 $\max\Big\{a,b,c,d\Big\} = \max\Big\{\max(a,b), \max(c,d)\Big\}$ 可知：

我们可以预处理出每列的行中最值，再对该列求一个最值，就是该 子矩阵 的最值

该 降维手段，使得一个 二维滑动窗口问题 变成了 n行+n列 的 一维滑动窗口问题

而 一维滑动窗口 我们可太熟悉了，直接套 单调队列 的模板即可

所以这题和 动态规划 有什么关系吗 QAQ

Code

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, k, res = 1e9;
int w[N][N], minv[N][N], maxv[N][N], que[N];
int a[N], b[N], c[N], d[N];

void get_max(int a[], int f[], int m)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= m; i ++ )
    {
        while (hh <= tt && i - que[hh] >= k) hh ++ ;
        while (hh <= tt && a[i] >= a[que[tt]]) tt -- ;
        que[ ++ tt] = i;
        f[i] = a[que[hh]];
    }
}
void get_min(int a[], int f[], int m)
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= m; i ++ )
    {
        while (hh <= tt && i - que[hh] >= k) hh ++ ;
        while (hh <= tt && a[i] <= a[que[tt]]) tt -- ;
        que[ ++ tt] = i;
        f[i] = a[que[hh]];
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    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_min(w[i], minv[i], m);
        get_max(w[i], maxv[i], m);
    }

    for (int i = k; i <= m; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            a[j] = maxv[j][i];
            b[j] = minv[j][i];
        }
        get_max(a, c, n);
        get_min(b, d, n);
        for (int j = k; j <= n; j ++ ) res = min(res, c[j] - d[j]);
    }
    printf("%d\n", res);
    return 0;
}

19 评论

lsp_同学 2024-05-14 17:37

这个图好形象呀！

cocoshe 2023-04-27 03:40

我试了下deque，用deque实现是会被卡时间嘛？好像TLE了

cocoshe 2023-04-27 03:41

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;

int n, m, k, a[N][N];
int row_min[N][N], row_max[N][N], b[N], c[N], d[N], e[N], ans=1e9;
deque<int> q;

void get_min(int a[], int row_min[], int m) {
    q.clear();
    for (int i = 1; i <= m; i ++ ) {
        if (q.size() && i - q.front() >= k) q.pop_front();
        while (q.size() && a[i] <= a[q.back()]) q.pop_back();
        q.push_back(i);
        row_min[i] = a[q.front()];
    }
}

void get_max(int a[], int row_max[], int m) {
    q.clear();
    for (int i = 1; i <= m; i ++ ) {
        if (q.size() && i - q.front() >= k) q.pop_front();
        while (q.size() && a[i] >= a[q.back()]) q.pop_back();
        q.push_back(i);
        row_max[i] = a[q.front()];
    }
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; i ++ ) {
        get_min(a[i], row_min[i], m);
        get_max(a[i], row_max[i], m);
    }

    for (int i = k; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            b[j] = row_min[j][i];
            c[j] = row_max[j][i];
        }
        get_min(b, d, n);
        get_max(c, e, n);

        for (int j = k; j <= n; j ++ ) 
            ans = min(ans, e[j] - d[j]);

    }
    cout << ans << endl;


    return 0;
}

etener 2023-08-19 15:40 回复了 cocoshe 的评论

你的代码+ (o)3优化就过了

AcKing. 2021-09-27 16:53

巨巨，我想请教一下。
for (int i = 1; i <= m; i ++ ) { while (hh <= tt && i - que[hh] >= k) hh ++ ; while (hh <= tt && a[i] >= a[que[tt]]) tt -- ; que[ ++ tt] = i; f[i] = a[que[hh]]; }
这个get_max里面，把最后一行移到第二行之前，就报错呀？

一只野生彩色铅笔 2021-09-27 17:02

$j$ 的范围应该是：$0 \le i-j \lt k$，所以求 $i$ 的最值时，要先把 $i$ 滑进当前的滑动窗口

具体一点来理解的话，计算以第 $i$ 哥元素为 右端点 的最大值，要算上第 $i$ 个元素

一只野生彩色铅笔 2021-09-27 17:04

这个分析也适用所有的 滑动窗口模型 问题

如果 $1 \le i - j$ 就要先算，再加

如果 $0 \le i - j$ 就要先加，再算

AcKing. 2021-09-27 18:59 回复了一只野生彩色铅笔的评论

感谢大佬指点！！！十分通透

AcKing. 2021-09-27 16:19

题解很清晰，彩铅大佬tql！！！

一只野生彩色铅笔 2021-09-27 17:02

谢谢大佬的夸奖 w

waydedie 2023-03-19 15:32

我不太理解关于tt=0和tt=-1有什么差别

糖豆 2023-06-14 10:19

tt=0：表示提前入队列了一个哨兵，此种情况一般与前缀和共同使用，因为计算s[9]-s[0]，就是获取1~9的前缀和，此时提前入队列一个哨兵，保证了所有数据的处理逻辑一致，否则就会造成对于第1个数据，它的处理逻辑与其它的不一致.
tt=-1：这是基础课中队列的标准姿势，就是普通的队列，没有加入哨兵。因为本题没有涉及到前缀和概念，不需要什么哨兵，而且，通过观察法，你就能知道，主体代码在没有初始入哨兵时才是正确的。

xyh2 2023-01-14 10:06

哈哈哈，牛逼大佬

zshzsh 2022-11-05 15:37

二维降到一维的过程有详细点的文章吗

陈平安 2021-10-03 22:21

佬，如果用minv[i][j]表示从(1,1)到(i,j)的最小值，行从k开始才是对的呢，从1开始就不对了呢，我是用一个二维数组minv[i][j]存储最大值，maxv[i][j]存储最大值，计算res是把单独提出了了。我的代码：
https://pastebin.ubuntu.com/p/2XChXt3bSq/
第51行标注了我的问题