I - 滑动窗口

题目

原题来自：POJ 2823

给一个长度为 N 的数组，一个长为 K 的滑动窗体从最左端移至最右端，你只能看到窗口中的 K 个数，每次窗体向右移动一位，如下图：

你的任务是找出窗体在各个位置时的最大值和最小值。

输入格式

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

输出格式

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

样例

Input

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

Output

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

数据范围与提示

对于 20% 的数据，K≤N≤1000；
对于 50% 的数据，K≤N≤10^5；
对于 100% 的数据，K≤N≤10^6。

思路

该题为单调队列的典型题。

如果纯暴力做的话，我们要从第一个元素一直历到第N个元素，每遍历一个元素都要再遍历框里面的元素，找出框里面的最大或最小值，这样的时间复杂是O(N×K)了，对于N和K都等于10^6时，时间已经爆了，所以我们要想一个更快速的做法，单调队列就是一个不错的选择。

就以样例中求每个框中的最小值为例：

单调队列首先要设头指针和尾指针（此指针非彼指针），还要建立一个队列数组，要注意的是队列数组中存的是元素的下标，而不是元素的值。

当框内元素还没到K个的时候，无法求得框内的最小值

当框移动到 i=3 的位置时

这时框内的最小值为-1，可存入队列中 ，这时候头指针指向了1，尾指针指向了2

当框移动到 i=4 的位置时

这时候新来的元素 -3 比头指针指向的 -1 还要小，所以要把 -1 踢出队列，踢出队列的方法就是让尾指针往前一格，这样下一次记录的时候就会将 -1 覆盖掉，就相当于把 -1 踢出去了

如此操作后队列就变成了

 当框移动到 i=5 的位置时

 

这时候新来的元素是 5 ，比 -3 大，所以按从小到大的队列顺序来排应该排到后面，只需将 5 正常插入进队列即可

如此操作后队列就变成了

 当框移动到 i=6 的位置时

 

这时候新来的元素是 3 ，比 -3 大，但比 5 要小，按顺序应该排到 5 前面，但是按照队列先进先出的特性，我们应该先把 5 踢出去，然后才能把 3 放进来，所以就按之前的操作一样，让尾指针往前走一格，然后将 3 存入即可

如此操作后队列就变成了

  当框移动到 i=7 的位置时

要注意的是这个时候 -3 已经不在框里面了，所以我们要将 -3 给踢出去，方法就是将头指针向后走一格，这样 -3 就不在队列的范围里面了，然后新来的元素是 6 ，比 3 大，所以排到3的后面

如此操作后队列就变成了

 

有些同学看到这里可能就会有疑问了，之前的 -1 去哪了？为了解决这个问题，我们进行实时输出就行了

if (i >= k)
{cout << a[q[head]] << " ";
}

再次提醒一下，队列 q 里面存的是元素的下标，所以输出队列内元素的时候是输出 a[q[head]]

同样的，求题目中要求的最大值就令队列的排序规则反过来即可，该方法的时间复杂度为O(N)。

代码

#include<iostream>
using namespace std;
int n, k, a[100005], q[100005], head, tail;
int main()
{cin >> n >> k;for (int i = 1; i <= n; ++i){cin >> a[i];}head = 1, tail = 0;for (int i = 1; i <= n; ++i){if (head <= tail && i - k + 1 > q[head])//头指针肯定在尾指针前面{++head;}while (head <= tail && a[i] < a[q[tail]]){--tail;}q[++tail] = i;//这里存入的是元素的下标if (i >= k)//只要框到位置了，就直接输出当前状态的最小值{cout << a[q[head]] << " ";}}cout << endl;head = 1, tail = 0;//重置一下头、尾指针的位置for (int i = 1; i <= n; ++i){if (head <= tail && i - k + 1 > q[head]){++head;}while (head <= tail && a[i] >= a[q[tail]]){--tail;}q[++tail] = i;if (i >= k){cout << a[q[head]] << " ";}}return 0;
}