Sliding Window Maximum

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 knumbers 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].

-----------------------------------------------------------------------------------------------------------------------

There are mainly two methods to solve this problem: PriorityQueue and Deque. Both two methods use O(k) space. But time complexity for PriorityQueue is O(nlogk) and O(n) for Deque.

Let's write the first method:

(1)  PriorityQueue

    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null || nums.length == 0) return new int[0];

        int[] res = new int[nums.length - k + 1];

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < nums.length; i++) {

            if (i >= k) pq.remove(nums[i-k]);

            pq.offer(nums[i]);

            if (i>=k-1) res[i+1-k] = pq.peek();

        }

        return res;

    }

(2) Deque

    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++) {

           // i - k is the left most element index. So it need to be removed when the window sided over 

            if (!deque.isEmpty() && deque.peek() == i-k) deque.poll();

           // make sure the deque is always decreasing

            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])

                deque.removeLast();

            // add the element to the end

            deque.offer(i);

            if (i>=k-1) res[i+1-k] = nums[deque.peek()];

        }

        return res;

    }