单调队列，顾名思义就是一个具有单调性的一个队列，可是该怎么实现呢。
用普通的队列肯定不能实现，因此我们需要用到里一个数据结构——双端队列，这个也比较容易理解，就是两头都可以进和出队的操作。
然后我们就可以进行愉快的写单调队列了。
单调队列与优先队列还不一样，优先队列只要你不主要删除，他是不会删的，但是单调队列不一样，只要不符合单调性，那先让不满足性质的数先出来，然后再加入这个不符合单调性的毒瘤。
举个例子
比如我们现在需要一个单调递增的队列，（注意这里的单调递增不是指队列里的值按照顺序单调递增，而是从队尾出队的时候要单调递增）
比如下面这个单调递增的队列：
5 3 2 1
接下来要从队尾添加一个数
分两种情况：
1：
- 然后如果我们加入了一个符合单调性的数，直接加就好了。
- 代码：
if(data[i] < q.back()) q.push_back(data[i]);
2：
- 反之，因为我们要使队列满足单调性，所以要先让不满足的数出队。
- 代码：
-
while(!q.empty() && data[i] > q.back()) q.pop_back();
然后将这个大毒瘤入队
- 代码：
q.push_back(data[i]);
这基本上就是单调队列的基本操作了，但是要灵活掌握，比如如果像是滑动窗口那样的题，可以入队编号，然后再通过编号来判断是否该编号在不在窗口里。
例题：
我们先分析一下这个题目，看上去可能就是一个需要优化的枚举罢了，但是该怎么枚举呢，我们就需要先简化一下题意。
就是我们把这n个点看最多有哪些点破环成链之后所有位置的前缀和都非负，可是这个又与单调队列什么关系呢，所谓破环成链，便是找到一个点，设这个点的位置为pos，则把1——pos的所有值都移到n + 1——n + pos +1上，这样就和题意相符了，这样还不够，因为我们还需要在规定的时间内完成任务，这就很尴尬了，就需要一个数据结构来加快速度，这里我们选用单调队列，因为我们只要判断前缀和的最小值减去sum[k-1]非负就好了。因为只要有一个点是负的，这个k就不行，就可以枚举下一个k了。
最终思路：
- 首先我们应该破环成链。
- 我们先预处理出所有前缀和。
3:然后对于每个点k，我们判断每个点的最小值与sum[k - 1]的关系。并统计个数。
代码:
#include#include #include #define M 1000010using namespace std;struct cym { int val, pos;}e[M];int sum[M], n, minn, tot;deque q;int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) { int x; scanf("%d", &x); sum[i] = sum[i - 1] + x; while(!q.empty() && q.back().val > sum[i]) q.pop_back(); q.push_back((cym){sum[i], i}); } for(int i = 1; i <= n; i++) { if(q.front().pos < i) q.pop_front(); if(q.front().val < sum[i - 1]) continue; minn = min(minn, sum[i - 1]); if(minn < sum[i - 1] - sum[n]) continue; tot++; } printf("%d", tot); return 0;}