LeetCode 239. Sliding Window Max

Leetcode : Sliding Window Maximum
Diffculty：Hard

关键字：滑动窗口，Deque

描述：
给一个数组 nums 和一个窗口大小 k 。
假定你只能看到窗口内的数字，每次窗口移动，滑动一格。
（k总是有效的， 1<= k <= nums.length ）

要求：
返回每次窗口中的数字的最大值，组成的数组。

举栗：
Input：nums=[1,3,-1,-3,5,3,6,7], k=3
OutPut: [3,3,5,5,6,7]

Explanation:

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

【要求】：在线性时间内解决问题

---

解题方法

一、堆排序。

这是我最先想到的办法。

具体思路：
可以构建k个元素的一个大顶堆。
每次滑动窗口，就相当于前一个元素出堆，后一个元素入堆。

时间复杂度：O(N logk)
比较接近线性时间了，但还是不够。
（代码太简单我就不写了，就是构建大顶堆，出堆和入堆）

二、使用Deque（双端队列）

在石杉的架构笔记看到的。

具体思路：
利用Java已有的双端队列，初始化一个Deque。该队列中保存的是 元素在nums中的索引值(index)。

滑动窗口时，保证：
1）往队列尾部追加节点时，要保证，该节点左边索引在num中的值，要始终大于右边的。如果不大于，则先把尾部节点逐个移除，直到满足条件，再往尾部追加节点。
保证队列的头节点索引所在的num值最大，并且严格按照向右递减

2）队列的头部节点的索引值，不能超出窗口范围。如果超出了，则移除该头节点。

3）由于队列头节点索引在num中的值是最大的，所以每次只要取头结点的值，然后根据该索引取num中的值即可。

话不多说，上代码：

    public static int[] maxSlidingWindow(int[] nums, int k){
        if(nums==null || nums.length<=0 ){
            return new int[0];
        }
        int[] res = new int[nums.length-k+1];
        Deque<Integer> deque = new LinkedList<>();
        for(int i=0; i<nums.length; i++){
            // 保证队列尾部的元素index 都比左边小.(也就是严格按从大到小value 的 index 顺序)
            while(!deque.isEmpty() && nums[i] >nums[deque.getLast()]){
                deque.removeLast();
            }

            // 向队列尾部添加元素(index)
            deque.addLast(i);

            // 移除超出窗口的头部元素(index)
            if(deque.getFirst() <= i-k){
                deque.removeFirst();
            }

            // 保存结果(当i移动到窗口大小时才开始保存结果)
            if(i>=k-1){
                res[i-k+1] = nums[deque.getFirst()];
            }
        }

        return res;
    }

LeetCode 执行结果：
RunTime：10ms (beats 76.37%)
Memory： 42.2MB (beats 65.32%)

---

参考：
石杉的架构笔记-滑动窗口面试题