例题参考洛谷P1886
问题简述：
一个数组，有一个滑动窗口，每一次滑动一个格子，求每次窗口内的最大值和最小值。
分析：
暴力要O（n^2）的复杂度，肯定会超时，这里会思考如何用空间换时间。
以最小值为例子，可以想到用一个数组维护最小值，扫数组一边就可以，如何实现呢？
这里可以用单调队列。
特性：存的是所有可能成为最小值的值的下标。队首是最小值的下标，单调递增（后面的数也有可能成为最小值）
为什么存下标？
因为需要解决两个问题：最小，在窗口内。
读取的原来的数组a存值，可以用来解决第一个问题，第二个问题就需要再写个存下标的数组
实现：
使用双端队列
- 每次去除队首过期的元素。
- 每次判断新元素和队尾元素的大小关系，如果比队尾的小，就弹走（它不可能成为最小值了，因为有一个比他又新又小的数出现了）
- 队首就是每一个窗口的最小值
- 对于最大值，可以用取相反数，转化成3的问题。
代码：
#include<cstdio>const int maxn = 1000000 + 10;int n, k;
int a[maxn];
int ans1[maxn], ans2[maxn];int head, rear;
int que[maxn];void solve(int res[]) {head = 1; rear = 0;for (int i = 1; i <= n; i++) {while (head <= rear && i - que[head] + 1 > k)que[head++] = 0;while (head <= rear && a[que[rear]] > a[i])que[rear--] = 0;que[++rear] = i;if (i >= k)res[i - k+1] = que[head];}
}int main() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);}solve(ans1);for (int i = 1; i <= n-k+1; i++)printf("%d ", a[ans1[i]]);printf("\n");for (int i = 1; i <= n; i++)a[i] = -a[i];solve(ans2);for (int i = 1; i <= n-k+1; i++)printf("%d ", -a[ans2[i]]);printf("\n");return 0;
}
STL双端队列实现：
#include<cstdio>
#include<deque>using namespace std;const int maxn = 1000000 + 10;
int a[maxn];
deque<int> dq;int n, k;
int ans1[maxn], ans2[maxn];void solve(int ans[]) {dq.clear();for (int i = 1; i <= n; i++) {while (!dq.empty() && i - dq.front() + 1 > k)dq.pop_front();while (!dq.empty() && a[dq.back()] > a[i])dq.pop_back();dq.push_back(i);if (i >= k)ans[i - k + 1] = dq.front();}
}int main() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);solve(ans1);for (int i = 1; i <= n - k + 1; i++)printf("%d ", a[ans1[i]]);printf("\n");for (int i = 1; i <= n; i++)a[i] = -a[i];solve(ans2);for (int i = 1; i <= n-k+1; i++)printf("%d ", -a[ans2[i]]);printf("\n");return 0;
}