滑动窗口内最大值和最小值的更新结构

问：窗口不管是 $L$ 还是 $R$ 滑动之后，都会让窗口呈现新状况，如何能够更快地得到窗口当前状况下的最大值和最小值？最好平均下来复杂度能做到 $O(1)$。

答：利用单调的双端队列。

---

双端队列：可以从队首进出队，也可以从队尾进出队。

示例：窗口内最大值的更新结构

严格规定双端队列从队首到到尾，存放的元素（存放的是数组下标）对应的值由大到小。

$R$ 往右滑动时，窗口内的最大值更新流程：

• 随着 $R$ 的滑动，从队尾插入数据；
• 当待插入的数据比此时队尾的数据大或者相等时，则弹出此时队尾的数据，新的数据从队尾入队。

$L$ 往右滑动时，窗口内的最大值更新流程：

• 随着 $L$ 的滑动，从队首弹出元素；
• 如果 $L$ 位置就是当前队首元素，则弹出；否则保留在队列中。弹出的元素已经过期，而此时的新队首就是新的窗口内的最大值。

之所以要在双端队列中存放下标，是因为根据下标可以得到对应的元素，且根据下标可以知道当前队列的队首是否过期。

此单调双端队列的含义：已经确定了目前窗口下单调双端队列的情况，如果此时依次让窗口缩小的话，哪些位置的数会依次成为窗口内的最大值。

优势：假设 $L$ 和 $R$ 会滑过数组中的每个数，则数组中的每个数最多都会进一次和出一次队，所以在窗口滑动的过程中，双端队列更新的总代价是 $O(n)$，均摊代价是$O(1)$，而每次得到的窗口状态就是双端队列的队首位置的元素，即查询代价是 $O(1)$。