滑动窗口

滑动窗口

#include<bits/stdc++.h>
using namespace std;
int s[10000], ans[10000];
deque<int> Q;
int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i=0; i<n; i++) {
		scanf("%d", &s[i]);
	}
	for(int i=0; i<n; i++) {
		if(!Q.empty() && i - Q.front() > k-1) Q.pop_front();
		while(!Q.empty() && s[i] < Q.back()) Q.pop_back();
		Q.push_back(i);
		ans[i] = s[Q.front()];
	}
	for(int i=k-1; i<n; i++) printf("%d ", ans[i]);
	Q.clear();
	for(int i=0; i<n; i++) {
		if(!Q.empty() && i - Q.front() > k-1) Q.pop_front();
		while(!Q.empty() && s[i] > Q.back()) Q.pop_back();
		Q.push_back(i);
		ans[i] = s[Q.front()];
	}
	cout << '\n';
	for(int i=k-1; i<n; i++) printf("%d ", ans[i]);
	return 0;
} 

题目意思：找出数组的每个k长度子区间的最大最小值。
按暴力枚举i，对每个[i, i+k]遍历，找最大最小复杂度 O(nk)。

用单调队列复杂度O(n)。
双端队列 deque，可以对前端后端都可以进行插入删除操作。

先把遍历时产生的各个队列列一下（找最大值）：

 1. 1
 2. 3
 3. 3 -1
 4. 3 -1 -3
 5. 5
 6. 5 3
 7. 6
 8. 7

我们观察发现我们每次都会把 s[i] 加进队列，队列中比s[i]小的都pop_back()出去了，剩下的形成了一个单调递减的队列，队列的头就是这个区间的最大值。
但还有特殊情况，例如：给出的s数组就是单调递减的，那上面形成的队列将像这样：

 1. 1 
 2. 1 2
 3. 1 2 3
 4. 1 2 3 4
 5. .......

解决方法：把数组的下标加入队列，这样比较队头元素与i的大小是否超过k-1，超过就pop_front()；