Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
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
Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?

Solution1：Heap (max)

思路：維護一個大小為K的最大堆，依此維護一個大小為K的窗口，每次讀入一個新數(shù)，都把堆中窗口最左邊的數(shù)扔掉，再把新數(shù)加入堆中，這樣堆頂就是這個窗口內(nèi)最大的值。
Time Complexity: O(NlogK) Space Complexity: O(K)

Solution：

思路： 遇到新的數(shù)時，
我們用雙向隊列可以在O(N)時間內(nèi)解決這題。當(dāng)我們遇到新的數(shù)時，將新的數(shù)和雙向隊列的末尾比較，如果末尾比新數(shù)小，則把末尾扔掉，直到該隊列的末尾比新數(shù)大或者隊列為空的時候才住手。這樣，我們可以保證隊列里的元素是從頭到尾降序的，由于隊列里只有窗口內(nèi)的數(shù)，所以他們其實就是窗口內(nèi)第一大，第二大，第三大...的數(shù)。保持隊列里只有窗口內(nèi)數(shù)的方法和上個解法一樣，也是每來一個新的把窗口最左邊的扔掉，然后把新的加進去。然而由于我們在加新數(shù)的時候，已經(jīng)把很多沒用的數(shù)給扔了，這樣隊列頭部的數(shù)并不一定是窗口最左邊的數(shù)。這里的技巧是，我們隊列中存的是那個數(shù)在原數(shù)組中的下標(biāo)，這樣我們既可以直到這個數(shù)的值，也可以知道該數(shù)是不是窗口最左邊的數(shù)。這里為什么時間復(fù)雜度是O(N)呢？因為每個數(shù)只可能被操作最多兩次，一次是加入隊列的時候，一次是因為有別的更大數(shù)在后面，所以被扔掉，或者因為出了窗口而被扔掉。
Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        int[] res = new int[nums.length + 1 - k];
        for(int i = 0; i < nums.length; i++){
            // 把窗口最左邊的數(shù)去掉
            if(i >= k) pq.remove(nums[i - k]);
            // 把新的數(shù)加入窗口的堆中
            pq.offer(nums[i]);
            // 堆頂就是窗口的最大值
            if(i + 1 >= k) res[i + 1 - k] = pq.peek();
        }
        return res;
    }
}

Solution2 Code：

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        LinkedList<Integer> deque = new LinkedList<Integer>();
        int[] res = new int[nums.length + 1 - k];
        for(int i = 0; i < nums.length; i++){
            // 滑動窗: 每當(dāng)新數(shù)進來時，如果發(fā)現(xiàn)隊列頭部的數(shù)的下標(biāo)，是窗口最左邊數(shù)的下標(biāo)，則扔掉
            if(!deque.isEmpty() && deque.peekFirst() == i - k) deque.poll();
            
            // 把隊列尾部所有比新數(shù)小的都扔掉，保證隊列是降序的
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.removeLast();
            
            // 加入新數(shù)
            deque.offerLast(i);
            
            // 隊列頭部就是該窗口內(nèi)第一大的
            if((i + 1) >= k) res[i + 1 - k] = nums[deque.peek()];
        }
        return res;
    }
}