· 题意

给定一个长度为 $n$ 的数组，求数组中区间 $[max(0, i - k + 1), i] (0 \le i < n)$中元素的最大值。

· 暴力

我们可以使用 队列 这种数据结构来维护这个长度为 $1~k$的区间，然后每次遍历整个队列，求一次最大值。

这样的时间复杂度是 $O(NK)$ 的，显然会超时。

· 优化

我们来仔细看一下队列中最大值的变化情况。

这里以样例为例子。

1. 1；最大值显然为1。
2. 1 3；最大值为3。
3. 1 3 -1；最大值为3。
4. 3 -1 -3；最大值为3。
5. -1 -3 5；最大值为5。

我们观察一下，会发现在第2次中$3$入队之后，$1$就再也没有用了。因为$3$比$1$后入队，说明只要$1$再队列中，$3$就一定在。而$3$和$1$肯定是$3$更大。

深入思考，我们会发现一旦有一个元素后入队，并且其值大于队列中的之前的数值的话，就可以将之前较小的数值弹出。

这样处理之后，显然队列中的元素都是单调递减的，故称单调队列。所以，最大值便是队首元素。

代码如下：

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    if (q[hh] <= i - k) hh ++ ;
    while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
    q[ ++ tt] = i;
    if (i >= k - 1) printf("%d ", a[q[hh]]);
}

其中，q是队列。

由于每个元素最多进出队列两次，故时间复杂度为 $O(N)$。

· 自问自答

Q：为什么弹出队列中元素时是从尾部弹出呢？队列弹出元素不是从队首弹出吗？
A：是的，但是这个优化后的单调队列不是最朴素的队列，它是双向队列，也就是STL中的deque。

Q：弹出小于等于$a_i$的元素时能从前往后遍历队列吗？
A：正确性上是没有问题的，但是这样会使时间复杂度退化为$O(NK)$。

【算法基础课】题解整合