Sliding Window Maximum 单调队列解区间最值

经典面试问题, 终于出现在Leetcode了, 写完后看了下discuss, 基本大家写的都差不多. 可见这题多容易考, 我身边的朋友就有被问过这题的.

题目很简单, 就是给一个大小为k的窗口, 然后给一个数组, 问在k下的最值是什么. 就用Leetcode的例子吧.

这题的解法好像有两种, 一种是双指针, 另一种是单调队列, 双指针判断corn case很复杂, 所以用单调队列比较简单, 代码短,面试才不容易出错.

单调队列是一个单调递增(递减)的队列, 这题中, 单调队列的大小为k.需要注意一下几点:

  1. 单调队列是一个双向队列, 所以可以用Dequeue 或者直接用LinkedList实现.
  2. 添加元素时, 从右(last) 往左(first) 添加, 添加的是数组的index, 因为下边我们需要通过比较index, 来判断是否过期.
  3. 添加元素前, 需要删除过期元素, 当判断一个元素是否过期时, 要从前往后判断, 因为前边的元素是队列中时序最”老”的元素. 并且判断时, 要比较最老元素的index和i-k+1的大小. i – k + 1是窗口[i-k+1,i]的最左边的index, 比如, 当i=6, 即在第6个元素时, 窗口左边的index为6-3+1 = 4, 所以窗口内最大可能的元素index为[4,5,6]
  4. 添加元素前, 需要删除比当前元素小的元素, 我们需要从队列的右边往左边 踢出元素, 因为队列是单调的, 右边的元素小于左边的元素. 所以通过踢出右边小于当前元素的元素, 保持队列单调.

代码如下: