Question:

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:

The array is [1 3 -1 -3 5 3 6 7], and w is 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

Input: A long array A[], and a window width w

Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]

Requirement: Find a good optimal way to get B[i]

// Option A: Using MaxQueue//// What is max queue, similar to max stackprivate static class MaxQueue{    private Queue
     
       queue = new LinkedList<>();    private Stack
      
        max = new Stack<>();        void offer(Integer t)    {        if (t == null)            return;        queue.offer(t);        if (max.empty() || t >= max.peek())            max.push(t);    }        Integer poll()    {        if (queue.isEmpty())            return null;                Integer t = queue.poll();        if (t >= max.peek())            max.pop();        return t;    }        Integer max()    {        if (max.empty())            return null;        return max.peek();    }}// Time: O(n)// Space: O(n + w)public int[] slidingWindowMax(int[] A, int w){    // Assumptions:    // A not null, not empty, length must >= w        // Init MaxQueue    MaxQueue maxQueue= new MaxQueue();    for (int i = 0 ; i < w ; i ++)    {        maxQueue.offer(A[i]);    }        // Result    int[] B = new int[A.length - w + 1];    B[0] = maxQueue.max();    for (int i = w ; i < A.length ; i ++)    {        maxQueue.poll();        maxQueue.offer(A[i]);        B[i - w + 1] = maxQueue.max();    }        return B;}/// Option B: Dequeue//// It has a better option without using extra stack.//// Time: O(n)// Space: O(n)public int[] slidingWindowMax(int[] A, int w){    // Deque    // See     //    // [end ... head]    // Order : >>    // Every time push new element into end, still keep the order    //    Deque
       
         queue = new LinkedList<>();        // Init deque    for (int i = 0 ; i < w ; i ++)    {        offer(queue, A[i]);    }        // Result    int[] B = new int[A.length - w + 1];    B[0] = max(queue);    for (int i = w ; i < A.length ; i ++)    {        queue.offer(A[i]);        B[i - w + 1] = max(queue);    }        return B;}private void offer(Deque
        
          queue, int t){    while (!queue.isEmpty() && queue.peekLast() <= t)    {        queue.pollLast();    }    queue.offerLast(t);}private void max(Dequeue
         
           queue){    return queue.peekFirst();}