前言

【基础】类文章是我在较忙的时候，无法提升能力，从而打牢基础的文章。此类文章不会写的很详细，大佬们可以直接略过此类文章。

经典例题——滑动窗口

本题树状数组和线段树是可解的，但是这里单调队列无疑是更快，更好写的一种方法。

如题所示，它每次询问的去见识连续的，故一定有一些技巧或性质可以让它更好解。

我们只看最小值
我们设一个双端队列 q，q 里面只保存至多 k 个数，也就是当前区间可能的最小值。

以下时对于 1 3 -1 -3 5 3 6 7 的解释

如 1，3，- 1 三个数，我们发现在加入 - 1 的时候，前面两个数在存在 - 1 及之后的区间内不可能作为最大的数，所以可以在加入 - 1 的时候直接弹出队列。通俗理解就是不仅能力差，而且年纪大了的人在后期是直接淘汰的（这里并没有对任何人的歧视，仅是为了加深大家理解）。

在加入 - 3 时同理，将 - 1 弹出。
加入 5 时由于 5 可以够到 [5 3 6] 这个区询问，而 - 3 却无法够到，所以 5 先保留。
加入 3 时，5>3，故将 5 弹出。
加入 6 时，- 3 已经成为了历史，不会对之后的答案产生任何影响了，故弹出。
加入 7 时，无事发生。

这里我们就能发现一个性质：deque 中的所有数字都是由大到小排列的。答案就是最小的那个数，也就是 q.front().sum

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000005];
struct kkk{
    int t,sum;
};
deque<kkk> q; 
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        kkk tmp;
        tmp.sum=a[i];
        tmp.t=i;
        if(q.empty()){
            q.push_back(tmp);
            continue;
        }
        if(i>k)printf("%d ",q.front().sum); 
        if(q.front().t+k<=i){
            q.pop_front();
        }
        while(!q.empty()&&q.back().sum>a[i]){
            q.pop_back();
        }
        q.push_back(tmp);
    }
    printf("%d\n",q.front().sum);
    while(!q.empty())q.pop_front();
    for(int i=1;i<=n;i++){
        kkk tmp;
        tmp.sum=a[i];
        tmp.t=i;
        if(q.empty()){
            q.push_back(tmp);
            continue;
        }
        if(i>k)printf("%d ",q.front().sum); 
        if(q.front().t+k<=i){
            q.pop_front();
        }
        while(!q.empty()&&q.back().sum<a[i]){
            q.pop_back();
        }
        q.push_back(tmp);
    }
    printf("%d",q.front().sum);
    return 0;
} 

估计之后文章中会讲单调队列优化 DP，就是以单调队列为基础的。