区间M的最小值

主要是是以题目的形式进行讲解

题目如上，

说说一开始的思路，当看到输出最小值内心想到的是小根堆，然后说区间内，这个区间是滑动的，那可以想到滑动窗口

总的来说：滑动窗口 + 递增序列 -> 单调递增队列！

注意队列中存放的是下标，目的是为了维护前m个数，意思就是这个区间内的数属于【i-m，i-1】，当下标小于i-m时，即说明这个数不属于这个区间，需要移除队列

那滑动窗口讲完了，该如何实现递增序列，嘿嘿嘿手动实现嘛，保证队首最小,加入的数也要比队尾小，先删除队尾 再加入新的小的数。同时给大家说明一下：我们实现这个题目时需要注意：先删除不应该在区间的值，再输出最小的值，最后加入新的值。

总结一下注意点：

1.deque存的是下标

2.实现时注意先使区间都是有效值，删掉不符合条件的

3.注意删的是队首还是队尾，加的是队首还是队尾

4.加入值时判断与队尾的大小，比他大就不加了，比他小时，注意先删再加**

代码如下（注意看注释）：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include<bits/stdc++.h> using namespace std; constintN = 2e6+5; inta[N]; intmain() { intn,m; cin>>n>>m; for(inti=1;i<=n;i++) { cin>>a[i]; } deque<int>q; for(inti=1;i<=n;i++) { //先删不符合条件的 while(!q.empty() && q.front()<i-m) { q.pop_front();//这里是删队首，因为不属于区间内 } //输出区间内的最小值 ，即队首 if(q.empty()) { cout<<0<<"\n"; } else { cout<<a[q.front()]<<"\n";//注意：deque内存的是下标，输出时记得用a[]输出 } //右移窗口，同时维护递增序列 while(!q.empty() && a[q.back()]>a[i]) { q.pop_back();//这里要先删除再加，否则加了再删会误删a[i]，删掉大的主要是维护递增序列 } q.push_back(i);//将小的放入队尾 } return0; }