POJ 2823 Sliding Windows(单调队列)

题目链接：
POJ 2823 Sliding Windows
题意：
有$n$个数，可以用一个长度为$k$的矩形框住连续的$k$个数，要求依次输出矩形在这$n-k+1$个位置的每个区间的最大值和最小值。
数据范围：$n\leq 10^6$
单调队列：
单调栈主要用于解决元素对所影响的区间长度，而单调队列主要用于解决给定区间的限制条件求出相应的元素。时间复杂度都是:$O(n)$
考虑求区间最大值的情况。模拟一个单调非递减队列。每次将队列首超出区间长度的元素出队列，然后从队列尾剔除比当前元素小的队列中的元素，因为维护的是单调非递减栈，此时队列首的元素就是区间最大值，因为每个元素最多只进一次队列，所以时间复杂度是$O(n)$的。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1000010;int n, k, total, Max_head, Max_tail, Min_head, Min_tail;
int data[MAX_N], que[MAX_N], Max[MAX_N], Min[MAX_N];int main()
{while (~scanf("%d%d", &n, &k)) {for (int i = 1; i <= n; ++i) {scanf("%d", &data[i]);}Max_head = Max_tail = Min_head = Min_tail = total = 0;for (int i = 1; i <= n; ++i) {// 队首表示元素在前，队中元素从队首到队尾从大到小排列while (Max_head != Max_tail && que[Max_head] <= i - k) {++Max_head;}// 从队尾开始排除较小的元素while (Max_head != Max_tail && data[que[Max_tail - 1]] <= data[i]) {--Max_tail; }// 在队尾添加新元素que[Max_tail++] = i;if (i >= k) {Max[total++] = data[que[Max_head]];}}total = 0;for (int i = 1; i<= n; ++i) {while (Min_head != Min_tail && que[Min_head] <= i - k) {++Min_head;}while (Min_head != Min_tail && data[que[Min_tail - 1]] >= data[i]) {--Min_tail;}que[Min_tail++] = i;if (i >= k) {Min[total++] = data[que[Min_head]];}}for (int i = 0; i < total; ++i) {if (i) printf(" ");printf("%d", Min[i]);}printf("\n");for (int i = 0; i < total; ++i) {if (i) printf(" ");printf("%d", Max[i]);}printf("\n");}return 0;
}