🍕 窗口

【窗口】： 就是两个边界 L 和 R ，并且 L 永远不会超过 R ，它们两个也永远只会往一个方向移动。

【目标】： 每次都能够很快的获取窗口内的最大值，方法是借助维护一个有序的双端队列 —— 一段是最大值，另一端是最小值。

【双端队列】： 两段都可以出。 里面存储的是窗口所在数组的值的下标。

双端队列维护流程：

• 如果 R 移动， 判断 R 指向的值是否能插入到双端列队的最小值后面，如果无法插入，则弹出双端队列的最小值。 总之，确保 R 指向的值进入后能够在最大值后面，或者它就是最大值。 注意，如果队列内的值和 R 指向的值一样，那也要将其弹出。也就是保证 双端队列的 "单调性"
• 如果 L 移动，如果 L 所在位置下标是双端队列中最大值下标，则弹出双端队列的最大值，不是，则不管。

双端队列维持的信息是： 如果当前 R 不再动， L 一直动，谁会是最大值。

为什么 R 移动时可以弹出双端队列中的值： 因为新的值肯定比旧的值晚过期，而且新的值还比旧的值大，所以弹出的值是不可能再成为最大值的了，所以可以弹出。 这也是为什么值相同时，也要将其弹出。 因为新的值更晚过期。

更新代价：数组中每一个元素最多进队列一次，最多出队列一次。所以总的代价是 O(N) ，平均代价是 O(1)。

上面讲的是最大值的情况，最小值的情况是同理的。