这么简单的题目我居然搞了两个小时。。。

题目

题目描述：
给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，如下图：
你的任务是找出窗体在各个位置时的最大值和最小值。

输入描述：
第1行：两个整数N和K；
第2行：N个整数，表示数组的N个元素（≤2×109）

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

解析

这道题目刚拿到手，我说：这不简单吗，不找个最大值一路跑过去吗？但这道题要求是区间内最大值，所以我们要思考一下了。
思考了许久~~~我就想到了（瞄了一眼邓老师的解析），就发现这道题这道题其实是一道单调队列（第一次听说。。。）。

算法讲解：
  1. 首先呢，这道题我们要知道，在一串的区间下去，我们要干什么？我们要知道每个区间的最大值和最小值。
  2. 按照我们的常理，极值都要重新遍历一遍去找，但是题目肯定是不会允许我们在O(n2)下完成这道题的。
  3. 那么我们的解题思路就应该从对每个区间求最大值，转变为在遍历一遍的情况下怎么判断某个数是否有用并记录。
  4. 所以这个时候我们就应该想到（我又没想到）：当我们有了一个较大值之后，前面比他小的值就全部没有意义了（最小值类同）。
  5. 所以在这里我们就应该逐个记录下元素，当遇到一个较大值时，就把前面比他小的全部删掉（这里以最大值举例）。
  6. 但是这里要注意一点：我们是有区间范围的，所以超出区间范围的值不应该算到答案里面去（例如你最大值在区间之前，就不应该算进去）。
  7. 所以我们这里要用到一个结构：双端队列：因为我们队首队尾都要进行操作。队首：删除区域外元素；队尾：添加元素并删除较小元素；

打代码咯：
  1. 我们先把我们的操作数组存下来（我一开始还想一步到位，现在发现自己是个傻缺）。
  2. 然后分别求出最小值集合和最大值集合（我们下面用最大值集合举例）。
  3. 首先我们要确定我们的双端队列要保存什么？这是个搞了我半个多小时的问题。我们保存的应该是下标而不是值。
  4. 为什么保存下标呢？因为我们只保存值的话，确实可以完成队尾的增添删减（因为只要比大小就行了）。
    但是我们无法知道队首值是否在区间外面。但是如果我们保存的是下标的话，求值我们可以靠数组索引。
  5. 既然基础都打好了，后面我们就好办了：只要进行队尾增删操作和队首控制界限操作就行了。
  6. 首先进行队列存储（队尾操作）：先判断队尾的元素是否比新增元素小，小就删除到比入队元素大为止。然后入队。
  7. 然后进行越界判断：判断队伍是否为空（初始K个的特判），并且当前最大值（队首元素）是否小于左边界（左边界我们用i - k，也就是i - k到i的范围），小就删掉。
  8. 最后存进预留的两个数组（最大值数组和最小值数组）中，输出就行了。
  9. 好了看代码吧~

AC代码 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false);
#define debug(t) cout << #t << " = " << t << endl;
//代码预处理区

const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int MAX = 1e6 + 7;
int f[MAX];
int que[MAX], front, len;
int mx[MAX], mn[MAX];
//全局变量区

template<class T>inline void read(T& res);
//函数预定义区

int main() {
    int N, K; read(N); read(K);
    for (int i = 1; i <= N; i++) read(f[i]);
    front = len = 0;
    for (int i = 1; i <= N; i++) {
        while (len && f[i] <= f[que[front + len - 1]]) len--;
        que[front + len++] = i;
        while (i > K && que[front] <= i - K) front++, len--;
        mn[i] = f[que[front]];
    }
    //求出最小序列
    front = len = 0;
    for (int i = 1; i <= N; i++) {
        while (len && f[i] >= f[que[front + len - 1]]) len--;
        que[front + len++] = i;
        while (i > K && que[front] <= i - K) front++, len--;
        mx[i] = f[que[front]];
    }
    //求出最大序列
    for (int i = K; i <= N; i++)
        if (K == i) printf("%d", mn[i]);
        else printf(" %d", mn[i]);
    printf("\n");
    for (int i = K; i <= N; i++)
        if (K == i) printf("%d", mx[i]);
        else printf(" %d", mx[i]);
    printf("\n");
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}