Description

滑动窗口

Input

第 1 行：两个整数N和K ；K<=N<=1000000 第 2 行：N个整数，表示数组的第N个元素(<=2*10^9)；

Output

第一行为滑动窗口从左向右移动到每个位置时的最小值，每个数之间用一个空格分开； 第二行为滑动窗口从左向右移动到每个位置时的最大值，每个数之间用一个空格分开。

输入数据 1

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

输出数据 1

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

思路：

这道题目的时间限制卡得比较紧，需要用 O(n)时间复杂度的算法来做。

这是一道单调队列的模板题，以求最小值为例：

我们从左到右扫描整个序列，用一个队列来维护最近 k 个元素；
如果用暴力来做，就是每次都遍历一遍队列中的所有元素，找出最小值即可，但这样时间复杂度就变成 O(nk) 了；
然后我们可以发现一个性质：
如果队列中存在两个元素，满足 a[i] >= a[j] 且 i < j，那么无论在什么时候我们都不会取 a[i] 作为最小值了，所以可以直接将 a[i] 删掉；
此时队列中剩下的元素严格单调递增，所以队头就是整个队列中的最小值，可以用 O(1)的时间找到；
为了维护队列的这个性质，我们在往队尾插入元素之前，先将队尾大于等于当前数的元素全部弹出即可；
这样所有数均只进队一次，出队一次，所以时间复杂度是 O(n) 的。

CODE：

//单调队列
#include
using namespace std;
int a[1000010],q[1000010];
int main() {
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	int head=1,tail=0;
	for(int i=1; i<=n; i++) {
		if(head<=tail&&i-k+1>q[head])
			head++;
		while(head<=tail&&a[q[tail]]>=a[i])//无法成为最小的
			tail--;
		q[++tail]=i;
		if(i>=k)
			printf("%d ",a[q[head]]);
	}
	printf("n");
	head=1,tail=0;
	for (int i=1; i<=n; i++) {
		if(head<=tail&&i-k+1>q[head])
			head++;
		while(head<=tail&&a[q[tail]]<=a[i])//无法成为最大的
			tail--;
		q[++tail]=i;
		if(i>=k)
			printf("%d ",a[q[head]]);
	}
	printf("n");

	return 0;
}

//双端队列
#include
using namespace std;
const int N=1e6+10;
int a[N],n,m,f,i,j,s_min[N],s_max[N];
deque min_val,max_val;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    min_val.push_front(1);
    max_val.push_front(1);
    s_min[1]=1;
    s_max[1]=1;
    m--;
    for(int i=2;i<=n;i++)
    {
        while (min_val.size() && min_val.front()+m=a[i])//生存能力弱,弹出
            min_val.pop_back();
        while (max_val.size() && a[max_val.back()]<=a[i])//生存能力弱,弹出
            max_val.pop_back();
        //if (a[i]<=min_val.front()) 生存能力,不只是看值的大小,还有位置问题
            min_val.push_back(i);
        //if (a[i]>=max_val.front()) 生存能力,不只是看值的小小,还有位置问题
            max_val.push_back(i);

        s_min[i]=min_val.front();
        s_max[i]=max_val.front();
    }
    for(int i=m+1;i<=n;i++)
        cout<