单调队列

单调队列是一种数据结构,顾名思义,它里面的元素都是单调递增或者单调递减的。用于实现类似滑动窗口类型的询问区间最值问题,当然也可以用ST表线段树等

但是单调队列在有些时候时空性能是最优的。

具体实现可以开一个Struct Monotone_queue

包含队首、队尾、id数组和value数组,当然value数组可以直接用id数组代替。

没读入一个数,就把他尽量的往队首放,我们保证每次询问时,队首都是最值答案,一旦队首编号超出范围就弹出队首

模板为洛谷的 单调队列

原文地址:https://www.cnblogs.com/delta-cnc/p/12811280.html