Sliding Window Maximum

Given an array of integers A. There is a sliding window of size B 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. You have to find the maximum for each window.
The following example will give you more clarity.

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


Return an array C, where C[i] is the maximum value of from A[i] to A[i+B-1].

Note: If B > length of the array, return 1 element with the max of the array.



Input Format

The first argument given is the integer array A.
The second argument given is the integer B.
Output Format

Return an array C, where C[i] is the maximum value of from A[i] to A[i+B-1]
For Example

Input 1:
    A = [1, 3, -1, -3, 5, 3, 6, 7]
    B = 3
Output 1:
    C = [3, 3, 5, 5, 6, 7]
Method:

maintain a monotonous queue: one end is always at max and the other end is min. Always need to return the max end of queue.
when adding new elements x: start from small-end of the queue, drop all smaller elements, then add new element to last
when sliding window: if the element to be dropped is the max element, drop it from the queue
 
Solution:

Time: O(n)
Space: O(n)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    private Deque<Integer> queue = new ArrayDeque<>();
    
    public ArrayList<Integer> slidingMaximum(final List<Integer> A, int B) {
        // [1, 3, -1, -3, 5, 3, 6, 7]
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < A.size(); i ++) {
            int val = A.get(i);
            if (i >= B && !queue.isEmpty() && queue.peekFirst().equals(A.get(i - B))) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && queue.peekLast() < val) {
                queue.pollLast();
            }
            queue.addLast(val);
            if (i >= B - 1) {
                result.add(queue.peekFirst());
            }
            // System.out.println(Arrays.toString(queue.toArray()));
        }
        return result;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] result = new int[n - k + 1];
        for (int i = 0; i < n; i ++) {
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}