239 Sliding Window Maximum *****unfamiliar with O(n) Deque

given an array and a window size, output the maximum number in the window

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. 
Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and 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
Note: 
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

First Solution : priorityqueue time O(logn)

follow up : solve it in linear time

 Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
     Window position                Max
     ---------------               -----
      0    1     2   3    4   5   6   7 
      1,   3,   -1,  -3,  5,  3,  6,  7
Rules :
Using Deque which is an two-end queue, combines the advantages of both queue and stack
we loop  through the element,
first we check if the first element in deque is still in valid range, for example, i = 3, k = 3, 
then deque should not contain index 0.
if deque.peekLast position number is less the curt number, then deque.removeLast, because the number before
the current larger number will no longer be strong candidates
and the number if less the the deque.peekLast we have to store the index, since it might be the largest for further
consideration.
if (i + 1 > k ) res[i + 1 - k] = nums[deque.peekFist()];
i = 0
deque 0 

i = 1
deque 1 

i = 2
deque 1 2


i = 3
deque 1 2 3 


i = 4 
deque 4 

i = 5 
deque 4 5

i = 6 
deque 6

i = 7
deque 7       
     [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].
     Deque : 存的是index 从大到小排序
     time : O(n)
     space : O(n)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null ||k == 0 || nums.length < k) {
            return new int[0];
        }
        int[] ans = new int[nums.length - k + 1];
        int index = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> b - a);
        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
            if (queue.size() == k) {
                ans[index++] = queue.peek();
                queue.remove(nums[i - (k - 1)]);
            }
        }
        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] a, int k) {
        if (a == null || k <= 0) {
            return new int[0];
        }
        int n = a.length;
        int[] r = new int[n-k+1];
        int ri = 0;
        // store index
        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < a.length; i++) {
            // remove numbers out of range k
            while (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            // remove smaller numbers in k range as they are useless
            while (!q.isEmpty() && a[q.peekLast()] < a[i]) {
                q.pollLast();
            }
            // q contains index... r contains content
            q.offer(i);
            if (i >= k - 1) {
                r[ri++] = a[q.peek()];
            }
        }
        return r;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k == 0 || nums.length  < k) {
            return new int[0];
        }
        Deque<Integer> deque = new LinkedList<>();
        int[] ans = new int[nums.length - k + 1];
        int index = 0;

        for (int i = 0; i < nums.length; i++) {
            // if the first index in deque is out of boundary k, remove it
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.poll();
            }
            //all number less than the current one, remove them
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offer(i);
            if (i + 1 >= k) {
                ans[index++] = nums[deque.peekFirst()];
            }
        }
        return ans;
    }
}