gyro永不抽风

ああああああああああああああああおおおおおおおおおおおおおおおお

P1886 滑动窗口 /【模板】单调队列

引言

再次写下这些东西,真的是感慨万千。从之前的只知道抄别人的,硬理解,到现在的查一下原理然后自己口胡,其中的辛酸大概也只有自己知道了。引用我很喜欢的一位数学老师的话:

只有体系建立起来了,才能办好事情。

单调队列的用途

一般来说,单调队列用在维护一个区间的极值上,即下面这两个式子:

正常情况下,时间复杂度应该为$O(mn)$。

单调队列的思想

单调队列,名为“单调”,意思就是队列当中元素是单调的。有一个很好的比方:你在排队买饭的时候,遇到比你弱的人,你就干掉然后插队,知道前面是比你强的人。这个时候你维护的就是一个单调递减的队列(因为你比你前面的人弱嘛),但是注意:你也在维护一个潜在的最大值的队列。

原因是这样的:当某个元素已经不在滑动窗口里面时,直接pop掉就行了,所以队首一定是区间最大值。

而区间最小值,只需要维护一个递增队列就行。

模板题目

题目描述

有一个长为 nn 的序列 aa,以及一个大小为 kk 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

例如:

The array is [1,3,1,3,5,3,6,7][1,3,-1,-3,5,3,6,7], and k=3k = 3

输入格式

输入一共有两行,第一行有两个正整数 n,kn,k。 第二行 nn 个整数,表示序列 aa

输出格式

输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

输入输出样例

输入 #1
8 3
1 3 -1 -3 5 3 6 7
输出 #1
-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明/提示

【数据范围】
对于 50%50\% 的数据,1n1051 \le n \le 10^5
对于 100%100\% 的数据,1kn1061\le k \le n \le 10^6ai[231,231)a_i \in [-2^{31},2^{31})

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;

const int maxn = 1000006;
int n, k, a[maxn];

struct node { int val, pos; } q[maxn];

signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> a[i];
int head = 0, tail = 0;
// find min -> increase
for (int i = 1; i <= n; i ++) {
while (head < tail && a[i] <= q[tail - 1].val) tail --;
q[tail ++] = (node) { a[i], i };
while (head < tail && i - q[head].pos + 1 > k) head ++;
if (i >= k) cout << q[head].val << (i == n ? "\n" : " ");
}
// find max -> decrease
head = 0, tail = 0;
for (int i = 1; i <= n; i ++) {
while (head < tail && a[i] >= q[tail - 1].val) tail --;
q[tail ++] = (node) { a[i], i };
while (head < tail && i - q[head].pos + 1 > k) head ++;
if (i >= k) cout << q[head].val << (i == n ? "\n" : " ");
}
return 0;
}
__EOF__
-------------本文结束感谢您的阅读-------------

本文标题:P1886 滑动窗口 /【模板】单调队列

文章作者:gyro永不抽风

发布时间:2020年09月20日 - 16:09

最后更新:2020年09月20日 - 17:09

原始链接:http://gyrojeff.moe/2020/09/20/P1886-%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 转载请保留原文链接及作者!

真的不买杯奶茶吗?T^T

欢迎关注我的其它发布渠道