题目一(滑动窗口的最大值)

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

算法思路

最简单的思路，就是遍历数组，找到所有的滑动窗口，耗时 O(n)，同时计算滑动窗口内的最大值，O(k)，那么总共需要 O(nk) 的时间复杂度。另一种思路是，引入队列，将滑动窗口内的数值存入，如果能够在 O(1) 内计算出队列中的最大值，那么算法也是可行的。
最后的思路是：不将滑动窗口内的每个数值都存入队列，而是将可能成为滑动窗口最大值的数值存入。那么，就要删掉那些队列中不可能成为滑动窗口最大值的元素。主要分为两类：一是队列中已有的数字小于待存入的数字；二是，队列中的队头如果滑出了窗口，也需要删除。那么，最终我们的队头就保存了滑动窗口的最大值。由于涉及了两段的删除，那么需要用到双端队列。并且我们需要知道当前队头的下标，以便知道滑动窗口的位置，因此队列中的元素不是数值而是数值的下标。

算法实现

题目二(队列的最大值)

定义一个队列并实现函数 max 得到队列里的最大值，要求函数 max、push_back 和 pop_front 的时间复杂度都是O(1)。

算法思路

思路类似题目一。在队列内部，除了一个保存原始数据的双端队列 data 外，还需要一个保存队列中最大值的双端队列 maxiums。当执行 push_back 时，maxiums仅保存可能成为队列最大值的元素，仍然需要比较待添加元素和 maxiums 队列中已有元素的大小关系。执行 pop_front 时，需要注意如果当前出队的元素恰好是当前队列中的最大值时(所以元素必须有个 index 值)，两个队列都必须出队头。
执行 max函数时，只需要返回最大值队列的队头即可。

算法实现

复杂度分析

算法一仅线性遍历数组，时间复杂度为 O(n)；利用了常数大小的队列，空间复杂度为 O(1)。

参考

[1] <<剑指offer2>>
[2] 牛客网