九章算法 | 微软面试题：滑动窗口的最大值

给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。

在线评测地址：LintCode 领扣

样例 1:

输入:
[1,2,7,7,8]
3
输出:
[7,7,8]

解释：
最开始，窗口的状态如下：`[|1, 2 ,7| ,7 , 8]`, 最大值为 `7`;
然后窗口向右移动一位：`[1, |2, 7, 7|, 8]`, 最大值为 `7`;
最后窗口再向右移动一位：`[1, 2, |7, 7, 8|]`, 最大值为 `8`. 

样例 2:

输入:
[1,2,3,1,2,3]
5
输出:
[3,3]

解释:
最开始，窗口的状态如下： `[|1,2,3,1,2 | ,3]` , 最大值为`3`;
然后窗口向右移动一位.`[1, |2,3,1,2,3]`, 最大值为 `3`; 

算法：单调队列

• 单调队列中的元素是严格单调的。我们在求解这个问题的时候需要维护他的单调性。
• 队首元素即为当前位置的最大值。假设要求滑动窗口中的最大值。我们就需要确保滑动窗口中的元素从队首到队尾是递减的。
• 每滑动一次就判断当前元素和队尾元素的关系，如果放入队尾满足单调递减，那么放入即可；如果放入不满足，就需要删除队尾元素直到放入当前元素之后满足队列单调递减。同时要确保已经出窗口的最大值（队首元素）被删除掉。

注意事项：

我们在本题中 往单调队列里压入的是元素对应的下标，因为我们要通过下标来判断该元素有没有离开了滑动窗口，如果离开了滑动窗口就得从队列里给删除了

流程

序列a是 1 2 7 7 6 5 3

滑动窗口的大小是3

遍历一遍 for i in 0：7

• i==0 队列里没有元素，直接添加（value=1,index=0） value是权值，index是下标（这里为了表达清晰，就把权值和下标都注明出来了）

队列里 (1,0)

• i==1 a[1]比队尾元素大，添加a[1]后不满足单调递减性质，所以需要把队尾给弹出，a[1]比队尾大，而且队尾元素肯定在a[1]的左面（因为队尾元素先压入的，它的下标肯定小），而且队尾元素还没a[1]大，对于后面的窗口，队尾元素肯定不是最大值了（我们已经找到了 a[1]比，而且队尾在窗口里面，a[1]肯定也在窗口里面，因为a[1]的下标更大）
  • 弹掉队尾后，队列为空
  • 压入(2,1)
  • 队列里 (2,1)
• i==2 a[2]比队尾元素大，弹掉队尾，压入(7,2)

队列里 (7,2)

这里i>=k-1了 ，当前队首为当前[0,2]这个滑动窗口的答案，这个窗口答案是7

• i==3 a[3]不比队尾元素大，不用弹出队尾 ，压入新元素

队列里 (7,2) (7,3)

统计[1,3]滑动窗口的答案，也是7

• i==4 a[4]不比队尾元素大，不用弹出队尾，压入新元素

队列里 (7,2) (7,3) （6，4）

统计[2，4]滑动窗口的答案，也是7

• i==5 a[5]不比队尾元素大，不用弹出队尾，压入新元素

队列里 (7,2) (7,3)（6，4）（5，5）

这时候i和队首位置差已经超过了滑动窗口长度，弹出队首

队列里 (7,3) （6，4）（5，5）

这个窗口答案也为7

复杂度分析

时间复杂度：每个元素进队出队都只有一次，所以复杂度是O(N)的

空间复杂度：队列里元素最多为N个,所以空间复杂度也是O(N)

public class Solution {
    /**
     * @param nums: A list of integers.
     * @param k: An integer
     * @return: The maximum number inside the window at each moving.
     */
    public List<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        // 答案数组和单调队列
        List<Integer> ans = new ArrayList<Integer>();
        Deque<Integer> qmax = new LinkedList<Integer>();
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            //维护单调性
            while(!qmax.isEmpty() && nums[i] > nums[qmax.getLast()])
                qmax.removeLast();
            //滑动窗口的长度超过了k 删掉超过的部分
            if(!qmax.isEmpty() && i - qmax.getFirst() >= k)
                qmax.removeFirst();

            qmax.addLast(i);

            //统计答案
            if(i >= k - 1) {
                ans.add(nums[qmax.getFirst()]);
            }
        }
        return ans;
    }
}

更多题解参考：九章算法