单调队列,hh是头,tt是尾,从头弹出,从尾进入
以下部分是构建滑动窗口的核心部分:
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;
while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
q[ ++ tt] = i;
if (i >= k - 1) printf("%d ", a[q[hh]]);
}
puts("");
首先前提一定是hh<=tt,头必须在尾的左边
如果滑动窗口过了hh,hh要向前走,怎样判断滑动窗口过了hh呢,i-k+1是滑动窗口的末尾,i-k+1>q[hh]则hh++
;
然后是while循环去元素的例子,while条件包括有东西hh<=tt和不满足a[q[tt]]>a[i]
,然后就要把队列中的元素去掉,去掉的方式很简单,t--
,入队列的方法也很简单,q[++tt]=i
(存的是i)
最后把队头给输出出来,注意一个i>=k-1,这个的意思是要等滑动窗口满了再输出