单调队列
思想
以寻找滑动窗口中的最小值为例
维护一个最小值的队列,队头为最小值,
将最新的数组元素加入队尾时,
将队列中比最新的数组元素小的元素从尾部出队,
这样我们就维护了一个有关最小值的单调递增队列
代码模板
//常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1,q[N];//q为单调队列,存储元素的下标
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
标签:队列,元素,hh,int,最小值,单调
From: https://www.cnblogs.com/fsh001/p/16817707.html