欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-11 12:09:32
...

WindowWindow

&\&

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

题目链接:

1. Window:jzoj 1326jzoj\ 1326
2.滑动窗口 /【模板】单调队列:luogu 1886luogu\ 1886

WindowWindow:

题目

给你一个长度为NN的数组,一个长为KK的滑动的窗体从最左移至最右端,你只能见到窗口的KK个数,每次窗体向右移动一位,如下表:
Window & 滑动窗口 /【模板】单调队列
你的任务是找出窗口在各位置时的 max value, min value.\ max\ value,\ min\ value.

输入

11nn , kk , 第22行为长度为nn的数组,每个数:2 ⁣ ⁣109 ⁣ ⁣2 ⁣ ⁣109-2\!*\!10^9\!\sim\!2\!*\!10^9

输出

22行,第11行每个位置的 min value\ min\ value,第22行每个位置的 max value\ max\ value

数据范围

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

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

题目

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

例如:

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

输入

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

输出

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

样例输入

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

样例输出

-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}])

思路与代码:

思路

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

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

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

(要用long longlong\ 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;
}