6-单调队列

算法思想

1. 使用普通队列求解问题
2. 使用单调队列优化解法

记忆口诀

1. 队头取值
2. 要最大，单调减，队头最大
3. 要最小，单调增，队头最小

算法模板

适用场景：找出滑动窗口中的最大值/最小值

// q 为什么不直接存储元素的值，
// 若存储元素的值，则 tt 指针无法回退
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
	// 若 tt >= hh，则单调队列的内容为 a[j], hh <= j <= tt
	// 若 tt < hh, 则单调队列的内容为 a[q[hh]];
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}