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

引言

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

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

单调队列的用途

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

$$dp[i] = \min_{i - m < j \leq i} \{ a[j] \}$$ $$dp[i] = \max_{i - m < j \leq i} \{ a[j] \}$$

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

单调队列的思想

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

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

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

模板题目

题目描述

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

例如：

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

输入格式

输入一共有两行，第一行有两个正整数 $n,k$。 第二行 $n$ 个整数，表示序列 $a$

输出格式

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

输入输出样例

输入 #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\%$ 的数据，$1 \le n \le 10^5$；
对于 $100\%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。

代码

#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;
}