题目大意
给出一段序列，一个长度一定的窗口从左到右滑动。求窗口滑动到每个位置时窗口内数字的最大值、最小值各是多少。n<=1e6。
总体思路
遇到这种对一个沿着一个方向滑动的区间求最值问题，可以运用单调队列优化。以求最小值为例。对整个序列构造一队列维护元素的下标，供多个窗口重复使用。设窗口左右端点各为l,r。要求对每个[l,r]，通过一些操作，使得该队列满足下列条件：
元素只属于[l,r]。从左到右下标对应的值必须是递增的。元素∈[l,r]的数量最多。
这样，该队列就会达到以下效果：
对于当前区间的最值，队首对应的值便是答案。保证以后的[l+1, r+1]区间要找最值就在这个队列里找，不会漏
这样每次遇到一个r，
不断从队首出队直到队首的下标>=l（满足条件1）将对应数大于r对应数的队尾元素从队尾弹出（满足条件2），将r入列（满足条件3).直接输出队首下标所对应数（利用条件2）
#include <cstdio>#include <cstring>#include <deque>#include <cstdarg>using namespace std;#define LOOP(i, n) for(int i=0; i<n; i++)const int MAX_N = 1000010;struct IntDeque{int a[MAX_N], head, tail;void clear() { head = tail = 0; }void push_back(int x) { a[tail++] = x; }void pop_back() { tail--; }void pop_front() { head++; }bool empty() { return head == tail; }int front() { return a[head]; }int back() { return a[tail - 1]; }};void Proceed(int*val, int n, int k , bool(*opt)(int,int)){static IntDeque pQ;pQ.clear();LOOP(curR, n){int curL = curR - k + 1;while (!pQ.empty() && pQ.front() < curL)pQ.pop_front();while (!pQ.empty() && opt(val[curR], val[pQ.back()]) )pQ.pop_back();pQ.push_back(curR);if (curL >= 0)printf("%d ", val[pQ.front()]);}printf("\n");}bool _lt(int x, int y){return x < y;}bool _gt(int x, int y){return x > y;}int main(){#ifdef _DEBUGfreopen("c:\\noi\\source\\input.txt", "r", stdin);#endifint n, k;static int val[MAX_N];memset(val, 0, sizeof(val));scanf("%d%d", &n, &k);LOOP(i, n)scanf("%d", i + val);Proceed(val, n, k,_lt);Proceed(val, n, k, _gt);return 0;}
