P1886 滑动窗口（单调队列）

--------------------------

题目链接：Miku

--------------------------

看一看这道题，我们很容易会发现采用模拟+遍历的方法会TLE

这时，我们就要采用这样一个东西了——单调队列(其实这也就是个单调队列模板）

---------------------------

单调队列，顾名思义，我们在使用时这个队列是有一定顺序（单调）的，并且它有一个特点，你的队列的极值一定在队首，知道这些，我们接可以做题了

---------------------------

单调队列是从队尾插入，而队首，队尾都会删除的双端队列。以该题为例，我们首先需要一个降序的单调队列，但是怎么实现呢？

假设此时队列为1，2，6，我们我们要插入一个4，显而易见，只要我们把4插进去，6就不可能是最小值了（反之就有可能），所以为了维护队列单调性，我们需要把6删除

    while(!q1.empty()&&q1.back()>=now)//注意，一定要把判断是否为空放在前面 
        {
            q1.pop_back();
            q2.pop_back();//弹出 
        }

example

看见提示了吗，在C++中，如果你返回一个空队列的值，就会RE，而且&&是短路运算符（简单来说，它会先判断左边的是否成立，成立再去判断右边），所以如果你反着放，c++会直接告诉你RE！而且右边的判断是否为空根本不会运算！！

------------------------

现在，你明白了单调队列的基本操作

------------------------

 1 /*
 2 其实有时候了解一些C++特性也挺重要的
 3 
 4 因为很多时候会RE而不知所措
 5 
 6 但是或许就和原理有关 
 7 */
 8 
 9 #include<iostream>
10 #include<queue>
11 #include<deque>
12 using namespace std;
13 deque <int> q1,q2;
14 int n,k;
15 int a[1000001];
16 int now;
17 int main(){
18     cin>>n>>k;
19     for(int i=1;i<=n;++i)
20     {
21         cin>>a[i];
22     }
23     //处理一个升序单调队列 
24     for(int i=1;i<=n;++i){
25         now=a[i];//当前值 
26         while(!q1.empty()&&q1.back()>=now)//注意，一定要把判断是否为空放在前面 
27         {
28             q1.pop_back();
29             q2.pop_back();//弹出 
30         }
31         q1.push_back(now);//压入 
32         q2.push_back(i);
33         if(i-k>=q2.front())//这是判断头元素是不是应该被“抛弃 
34         {
35             q1.pop_front();
36             q2.pop_front();
37         }
38         if(i>=k)//输出，一定要到了K在开始
39         //你一定明白 
40         {
41             cout<<q1.front()<<" ";
42         }
43     }
44     cout<<endl;
45     q1.clear();
46     q2.clear();//清空 
47         for(int i=1;i<=n;++i){
48         now=a[i];
49         while(!q1.empty()&&q1.back()<=now)
50         {
51             q1.pop_back();
52             q2.pop_back();
53         }
54         q1.push_back(now);
55         q2.push_back(i);
56         if(i-k>=q2.front())
57         {
58             q1.pop_front();
59             q2.pop_front();
60         }
61         if(i>=k)
62         {
63             cout<<q1.front()<<" ";
64         }
65     }
66     return 0;
67 }
68

-----------------------

That is all.