单调队列（滑动窗口）

题目描述

ZJM 有一个长度为 n 的数列和一个大小为 k 的窗口, 窗口可以在数列上来回移动. 现在 ZJM 想知道在窗口从左往右滑的时候，每次窗口内数的最大值和最小值分别是多少. 例如：
数列是 [1 3 -1 -3 5 3 6 7], 其中 k 等于 3.

Input
输入有两行。第一行两个整数n和k分别表示数列的长度和滑动窗口的大小，1<=k<=n<=1000000。第二行有n个整数表示ZJM的数列。

Output
输出有两行。第一行输出滑动窗口在从左到右的每个位置时，滑动窗口中的最小值。第二行是最大值。

求解思路

单调队列=队列里的元素满足出队的单调性，与单调栈的区别在于单调栈是面向全体的，单调队列是面向局部的。
单调递增队列:

• 如果队列为空或队尾元素小于入队元素，则入队
• 要将不满足条件的队尾元素全部出队后，将入队元素入队

单调递减队列

• 如果队列为空或队尾元素大于入队元素，则入队
• 要将不满足条件的队尾元素全部出队后，将入队元素入队

从第k个元素开始，每进行一次入队操作后，判断当前队首元素与入队元素下标的距离，若队首元素下标大于入队元素下标-k，则该元素为最大或最小值，若队首元素下标小于等于入队元素下标-k，弹出队首元素，继续判断当前队首元素，直到找到最值，窗口继续滑动，进行下一次入队操作，重复前述过程。

代码

#include<stdio.h>
#include<iostream>
#include <algorithm>
#include<string>
#include<string.h>
using namespace std;

int arr[1000005];
int que[1000005];
int con[1000005];//小的
int mon[1000005];//大的
int n, k;
void funcl()//单增队列
{
	int l = 0, r = -1;
	for (int i = 0; i < k-1; i++)
	{
		while (l <= r && arr[que[r]] > arr[i])
		{
			que[r] = i;
			r--;
		}
		r++;
		que[r] = i;
	}


	for (int i = k-1; i < n; i++)
	{
		while (l <= r && arr[que[r]]>arr[i])
		{
			que[r] = i;
			r--;
		}
		r++;
		que[r] = i;
		while (l <= r)
		{
			if (i - que[l] + 1 <= k)
			{
				con[i] = arr[que[l]];
				break;
			}
			l++;
		}

	}
}


void func2()//单减队列
{
	int l = 0, r = -1;
	for (int i = 0; i < k-1; i++)
	{
		while (l <= r && arr[que[r]] < arr[i])
		{
			que[r] = i;
			r--;
		}
		r++;
		que[r] = i;
	}


	for (int i = k-1; i < n; i++)
	{
		while (l <= r && arr[que[r]] < arr[i])
		{
			que[r] = i;
			r--;
		}
		r++;
		que[r] = i;
		while (l <= r)
		{
			if (i - que[l] + 1 <= k)
			{
				mon[i] = arr[que[l]];
				break;
			}
			l++;
		}

	}
}




int main()
{

	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
	funcl();
	func2();
	for (int i = 2; i < n; i++)
	{
		printf("%d ",con[i]);
	}
	printf("\n");
	for (int i = 2; i < n; i++)
	{
		printf("%d ", mon[i]);
	}
}