239. Sliding Window Maximum

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position.

For example,
Givennums=[1,3,-1,-3,5,3,6,7], andk= 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 assumekis always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Analysis:

Approach#1: (non-linear Complexity: nlogk)

have a maxHeap size of K, every time it slides, we poll from maxheap if the element suppose to be deleted(left most side of the window in last round) equals to maxheap.peek(), then we offer the new element in, do a poll and add the poll to returnArray.

Approach#2: (o(n))

have a deque to store index(not actual value)

1. for every new element comes in(to be added to tail), we look at tail, if tail smaller than new element, we pollLast() (remove tail), so we know that at any moment, if we peek() from the left side, we always get the max value.
2. when window start sliding, we remove from left for those out side of window
3. every round, we just need to offer new index in deque, and add nums[deque.peek()] into return array

Code: (approach #2)

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

            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            {
                deque.pollLast();
            }

            deque.offer(i);
            if(i >= k-1)
            {
                returnArray[index++] = nums[deque.peek()]; //peek from left side, and it should be max
            }

        }
        return returnArray;
    }
}