滑动窗口 Week5作业D题

题目：

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

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

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

样例：
Input:

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

Output:

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

思路:

本题考查单调队列。
要求查找窗口内的最小值, 是一个局部的概念。
求最小值：维护一个单调递增队列， 队列中的元素均属于当前窗口，当元素不属于当前窗口时, 将队首元素弹出即可。
求最大值同理。
当区间长度为1时，直接输出。

代码：

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

deque<int> q;
int n,k;
int a[1000050];

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	if(k==1)
	{
		for(int i=1;i<=n;i++)
		    cout<<a[i]<<" ";
		cout<<endl;
		for(int i=1;i<=n;i++)
		    cout<<a[i]<<" ";
		return 0;
	}
	else{
		
	for(int i=1;i<=n;i++)
	{
		if(i-q.front()==k) q.pop_front();
		if(q.empty()||a[i]>=a[q.back()]) q.push_back(i);
		else
		{
			while(!q.empty()&&a[i]<a[q.back()])
			q.pop_back();
			q.push_back(i);
		}
		if(i>=k) cout << a[q.front()] << " ";
	}
	cout<<endl;
	
	while(!q.empty()) q.pop_back();
	for(int i=1;i<=n;i++)
	{
		if(i-q.front()==k) q.pop_front();
		if(q.empty()||a[i]<=a[q.back()]) q.push_back(i);
		else
		{
			while(!q.empty()&&a[i]>a[q.back()])
			q.pop_back();
			q.push_back(i);
		}
		if(i>=k) cout << a[q.front()] << " ";
	}
	
	}

	
	return 0;
}