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

$Window$Window

$\&$&

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

题目链接：

1. Window：$jzoj\ 1326$jzoj 1326

2.滑动窗口 /【模板】单调队列：$luogu\ 1886$luogu 1886

$Window：$Window：

题目

给你一个长度为$N$N的数组，一个长为$K$K的滑动的窗体从最左移至最右端，你只能见到窗口的$K$K个数，每次窗体向右移动一位，如下表：

你的任务是找出窗口在各位置时的$\ max\ value,\ min\ value.$ max value, min value.

输入

第$1$1行$n$n , $k$k , 第$2$2行为长度为$n$n的数组，每个数：$-2\!*\!10^9\!\sim\!2\!*\!10^9$−2∗109∼2∗109

输出

$2$2行，第$1$1行每个位置的$\ min\ value$ min value,第$2$2行每个位置的$\ max\ value$ max value

数据范围

数据范围：
$20\%： n\!<=\!500;$20%：n<=500;
$50\%： n\!<=\!100000;$50%：n<=100000;
$100\%： n\!<=\!1000000;$100%：n<=1000000;

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

题目

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

例如：

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

输入

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

输出

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

样例输入

8 3
1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7

数据范围

对于 $50\%$50% 的数据，$1 \le n \le 10^5$1≤n≤105；
对于 $100\%$100% 的数据，$1\le k \le n \le 10^6$1≤k≤n≤106，$a_i \in [-2^{31},2^{31}])$ai​∈[−231,231])。

$思路与代码：$思路与代码：

思路

这道题就是一道单调队列。

我们先要去输出最小的，就我们就维护一个从小到大的数组，每次都插入当前的那个数，然后把在它前面比它大的数给踢掉。（因为要插入这个数而且又要维护数组从小到大）然后我们在踢出一个数，这时候不是踢出数组中的数，而是要看踢出的数是不是数组中的第一个数（因为这个数可能在读入的时候就被踢掉了）

而我们要输出最大的，就是和输出最小的相反的就是了。
（即从小变大变成从大变小，踢掉比它大的变成踢掉比它小的）

（要用$long\ long$long long）

代码

#include<cstdio>
#define ll long long

using namespace std;

struct node {
	ll num, x;
}f[1000001];
ll n, k, a[1000001], h, t;

int main() {
	scanf("%lld %lld", &n, &k);//读入
	
	for (int i = 1; i <= n; i++) 
		scanf("%lld", &a[i]);//读入
	
	h = 1;//初始化
	t = 0;
	for (ll i = 1; i <= n; i++) {
		while (a[i] <= f[t].x && t >= h) t--;//维护从小到大的数组
		f[++t] = (node){i, a[i]};//插入
		if (i >= k) {
			while (h <= t && f[h].num + k - 1 < i) h++;//踢出队列
			printf("%d ", f[h].x);//输出
		}
	}
	
	putchar('\n');
	
	h = 1;//初始化
	t = 0;
	for (ll i = 1; i <= n; i++) {
		while (a[i] >= f[t].x && t >= h) t--;//维护从大到小的数组
		f[++t] = (node){i, a[i]};//插入
		if (i >= k) {
			while (h <= t && f[h].num + k - 1 < i) h++;//踢出队列
			printf("%d ", f[h].x);//输出
		}
	}
	
	return 0;
}