单调队列两种模板

作者：

闪回 , 2024-03-23 08:44:54 , 所有人可见 , 阅读 71

第一种：不需要设置哨兵

hh = 0,tt = -1;
for(int i = 0;i<n;i++)
{
    if(hh <= tt && i - k + 1 > q[hh])hh++;
}

hh = 0,tt = 0;//哨兵不初始化的话是0
for(int i = 1;i<=n;i++)
{
    if(hh <= tt && i - k > q[hh])hh++;
}

羽笙 8个月前

之前一直疑惑i - k + 1 > q[hh]和i - k > q[hh]为什么不一样，现在明白了，因为需要具体问题具体分析，第二种是求不包括自己的滑动窗口的最值，而第一种是包含自己的滑动窗口的最值问题

skymiles 4个月前

可以详细帮举个例子吗～