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

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

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

    单调队列解区间最值
    nums  输入数组
    k  队列窗口大小
   Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

    Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

这题的解法好像有两种, 一种是双指针, 另一种是单调队列, 双指针判断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. 添加元素前, 需要删除比当前元素小的元素, 我们需要从队列的右边往左边 踢出元素, 因为队列是单调的, 右边的元素小于左边的元素. 所以通过踢出右边小于当前元素的元素, 保持队列单调.

代码如下:

public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || nums == null)
            return new int[]{};
        int n = nums.length;
        int[] res = new int[n - k + 1]; // 结果
        int p = 0;
        LinkedList<Integer> queue = new LinkedList<Integer>(); // 双向queue, 这里用linkedlist了. 也可以用Dequeue
        for (int i = 0; i < nums.length; i++) {    
            //窗口大小为k, 所以 i-k+1为在位置i上的窗口, 踢出所有窗口外的元素, 因为队列是从尾部添加的, 所以我们踢出头部的元素
            while (!queue.isEmpty() && queue.peekFirst() < i - k + 1)
                queue.removeFirst();
            //踢出所有小于当前元素的元素, 这里要从尾部踢出, 是因为尾部的元素是按照扫描的顺序添加的并且,大小为递减添加的.
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i])
                queue.removeLast();
            // 添加到尾部.
            queue.addLast(i);
            if (i >= k-1)// 当窗口未完全展开时, 不记录元素. 
                res[p++] = nums[queue.peekFirst()];
        }
        return res;
    }