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

题目：

P1091 [NOIP2004 提高组] 合唱队形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1091?contestId=138150

思路：

单调队列。

1.用数组模仿队列，dp[h]表示单调队列的头，dp[t]表示单调队列的尾。

2.队列只会存储可能成为k个数据中的最小值和最大值的下标（掠过的数据从队头出，比刚入队小（或者大）的数据从队尾出（不可能成为最大或者最小，没必要记录下来，dp中只会存储可能成为k个数据中的最小值和最大值的下标）

3.注意：因为是用数组dp模拟队列，所以2中的出并非真的将其从数组中踢出，而是借助头尾指针h,t的移动表示出。只有h,t之间的数据才表示单调队列里的数据。

代码：

//单调队列
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const ll N = 1000010;
int a[N], dp[N];
int main()
{
	ll n, k,i;
	cin >> n >> k;
	for (i = 1; i <= n; i++)scanf("%d", &a[i]);
	
	//维持窗口的最小值
	int h = 1, t = 0;//清空队列
	for (i = 1; i <= n; i++) {
		while (h <= t && a[dp[t]] >= a[i])t--;//尾出
		dp[++t] = i;//尾进(dp[]储存的是a[i]的下标i)
		if (dp[h] < i - k + 1)h++;//头出
		if (i >= k)cout << a[dp[h]]<<" ";//输出最小
	}
	cout << endl;
	//维持窗口的最大值
	h = 1, t = 0;//清空队列
	for (i = 1; i <= n; i++) {
		while (h <= t && a[dp[t]] <= a[i])t--;//尾出
		dp[++t] = i;//尾进(dp[]储存的是a[i]的下标i)
		if (dp[h] < i - k + 1)h++;//头出
		if (i >= k)cout << a[dp[h]] << " ";//输出最大
	}
}