洛谷：P1886 滑动窗口 之 （彻底搞懂单调队列）_滑动窗口洛谷

传送门：P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1886

一、题目描述

 

二、思路

滑动窗口和求m区间内的最小值的求解过程一样，都是运用单调队列求解，当然也可以运用其他方法求解，滑动窗口比起求m区间内的最小值多了个求最大值，那我们可以写两个函数，一个求最小值，一个求最大值，函数总的内容是一样的，只需要修改队尾的判断条件，具体求解过程请参考求m区间内的最小值。

洛谷：P1440 求m区间内的最小值_´悠 子ᴗ`-_-╭☞ꪗꪖꪑ的博客-CSDN博客

下面我们来了解什么是单调队列：

单调队列，顾名思义，是一种具有单调性的队列。众所周知，单调性有单调递增和单调递减两种，相应的单调队列也分为单调递增队列和单调递减队列两种。

单调递增队列：保证队列头元素一定是当前队列的最小值，用于维护区间的最小值。

单调递减队列：保证队列头元素一定是当前队列的最大值，用于维护区间的最大值。

实现流程：

实现单调队列，主要分为三个部分：

去尾操作 ：队尾元素出队列。当队列有新元素待入队，需要从队尾开始，删除影响队列单调性的元素，维护队列的单调性。(删除一个队尾元素后，就重新判断新的队尾元素)
去尾操作结束后，将该新元素入队列。

删头操作 ：队头元素出队列。判断队头元素是否在待求解的区间之内，如果不在，就将其删除。（这个很好理解呀，因为单调队列的队头元素就是待求解区间的极值）

取解操作 ：经过上面两个操作，取出 队列的头元素 ，就是 当前区间的极值 。

题解：

题目要我们求得极大值和极小值，那我们可以用一个单调递增队列和一个单调递减队列分别去维护k区间内的最大值和最小值。

下面来演示一下具体过程：

如案例 n=8,k=3 {1,3,-1,-3,5,3,6,7}

先求k区间的极大值

void max_windows() //找k区间内最大值
{
	front = 1;
	rear = 0;
	for (int i = 1; i <= n; i++)
	{
		while (q[front] <= i - k && front <= rear) //保证队首在k区间
			front++;
		while (front <= rear && a[q[rear]] <= a[i]) //维护k区间的单调性
			rear--;
		q[++rear] = i;    //入队
		if (i >= k)
			cout << a[q[front]] << " ";
	}
	cout << endl;
}

 

再求k区间极小值：

void min_windows()  //找k区间内最小值
{
	front = 1;
	rear = 0;
	for (int i = 1; i <= n; i++)
	{
		while (q[front] <= i - k && front <= rear) //保证队首在k区间
			front++;
		while (front <= rear && a[q[rear]] >= a[i]) //维护k区间的单调性
 
			rear--;
		q[++rear] = i; //入队
		if (i >= k)
			cout << a[q[front]] << " ";
	}
	cout << endl;
}

从上面求极大值和极小值的表格可以看出，单调队列不仅维护了区间k单调性，还实现了，队首就是要找的极大值或极小值。

三、代码区

#include <iostream>
using namespace std;
int q[1000005], a[1000005], front, rear, n, k;
 
void max_windows() //找k区间内最大值
{
	front = 1;
	rear = 0;
	for (int i = 1; i <= n; i++)
	{
		while (q[front] <= i - k && front <= rear) //保证队首在k区间
			front++;
		while (front <= rear && a[q[rear]] <= a[i]) //维护k区间的单调性
			rear--;
		q[++rear] = i;    //入队
		if (i >= k)
			cout << a[q[front]] << " ";
	}
	cout << endl;
}
 
void min_windows()  //找k区间内最小值
{
	front = 1;
	rear = 0;
	for (int i = 1; i <= n; i++)
	{
		while (q[front] <= i - k && front <= rear) //保证队首在k区间
			front++;
		while (front <= rear && a[q[rear]] >= a[i]) //维护k区间的单调性
 
			rear--;
		q[++rear] = i; //入队
		if (i >= k)
			cout << a[q[front]] << " ";
	}
	cout << endl;
}
int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	min_windows();
	max_windows();
	return 0;
}

 

     如果有什么不懂的地方可以在评论区留言！