int hh = 0, tt = -1;
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;
}
这段代码是一个单调队列的实现,用于解决滑动窗口问题。
初始化队列为空,队头指针为0
,队尾指针为-1
。
遍历所有元素i
(假设有n个元素),依次将它们压入队列中。
在每次插入新元素i
之前,先判断当前队头是否需要弹出。如果需要,则一直弹出,直到队头不再满足条件。这里check_out
函数是一个自定义的判断函数,用于判断当前队头是否已经滑出窗口范围。
在保证队列非空的情况下,不断弹出比新元素i
小且已经滑出窗口范围的元素。这里check
函数同样是一个自定义的判断函数,用于判断当前元素i
和队尾元素q[tt]
之间的关系。
将新元素i
压入队列中,并更新队尾指针tt
。 这段代码的核心思想也是维护一个单调递增(或递减)的序列,在遍历过程中不断将不符合要求的元素弹出,从而得到符合要求的最大(或最小)值。常见应用包括求解滑动窗口最大/最小值等问题。