我们发现上面的时间复杂度是O(N)，大大的优化了时间。

二、单调队列

1、什么是单调队列

单调队列就是队列中的元素具有单调性的队列。

2、单调队列模板

（1）问题

（2）分析

我们以最小值为例：

这道题我们同样可以采用暴力的做法：两个for循环相互嵌套。我们发现这种情况的时间复杂度是O(N²)。很明显，这种算法是非常低效的。

那么我们换一种算法：

我们先来思考一下，这道题适合什么样的数据结构？不难发现，这个滑动窗口是从前向后移动，即先进先出。所以我们想到了队列这种数据结构来存储。

那么队列是在队头输出的，因此我们需要保证队头输出的数据是最小值。此时受到刚才单调栈的影响，我们很容易想到这里应该是构造一个单调递增的队列，这样我们就能够保证队列中的第一个元素是最小的。

此时大家就会有一个疑问，为什么必须单调呢？我们明明只需要保证第一个最小即可。那么我们假设第一个是最小的，第二个是最大的。当我们的第一个元素滑出窗口的时候，第二个元素成为了第一个元素，此时第一个元素就不再是最小的。因此，我们保证单调性的时候，就能够保证每个元素做队头的时候，都小于后续的元素。

我们如何实现呢？单调递增的特点就是前一个元素小于该元素。接着我们就能写出下列的步骤：

• step1 : 在队列不为空的条件下，判断第一个元素是否在窗口内。
• step2 : 若队尾元素大于等于目标元素则删除
• step3 ：目标元素进队。

在进行步骤1的判断的时候，我们需要一个计数器去记录，但是这样是相当麻烦的，因此我们将下标存储到队列中，这样的话，我们就能够通过下标的方式去判断队头是否出队。

我们还是解决一下几个问题：
为什么要不满足单调性的元素可以删除？

在这个队列中，只要有3的存在，4必不可能是答案，那么当3不存在的时候呢？那么4更不可能是答案了，因为我们是在队头删除元素的。所以3出队的前提是4出队。因此只有4没有3的情况是不存在的。所以我们可以删除。

那么为什么目标元素一定要进队呢？
因为经过单调性的处理，目标元素就成了队中最大的，虽然目标元素队前的元素比其要小，但是他们都是先出队的，所以当前面的元素都出队的时候，该目标元素有可能成为答案，所以我们要让每个目标元素的下标都进队。

#include
using namespace std;
const int N=1000010;
int a[N],q[N],h,t;
int main()
{int n,k;cin>>n>>k;for(int i=0;iscanf("%d",a+i);if(h<=t&&q[h]=a[i])t--;q[++t]=i;if(i-k+1>=0)printf("%d ",a[q[h]]);}puts("");h=0,t=-1;for(int i=0;iif(h<=t&&q[h]=0)printf("%d ",a[q[h]]);}return 0;
}

我们发现，判断单调性的时候，我们是在队尾删除，判断是否在窗口内的时候，是在队头删除的。所以这不是普通的队列，而是双端队列，即STL中的deque。所以我们可以通过deque容器来实现。

#include
#include
#include
using namespace std;
int main()
{int n,k,b;cin>>n>>k;vectora;dequeq;for(int i=0;iscanf("%d",&b);a.push_back(b);if(!q.empty()&&q.front()=a[i])q.pop_back();q.push_back(i);if(i-k+1>=0)printf("%d ",a[q.front()]);}puts("");q.clear();for(int i=0;iif(!q.empty()&&q.front()=0)printf("%d ",a[q.front()]);}return 0;
}