Leetcode: 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 k numbers 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].

Note: 
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Hint:

1. How about using a data structure such as deque (double-ended queue)?
2. The queue size need not be the same as the window’s size.
3. Remove redundant elements and the queue should store only elements that need to be considered.

Understand the problem:
If the problem is solved by using a heap, the complexity would be n logk. 
Since the problem asks for liner time solution, we can use a deque. 

We enqueue the element from the end of the deque, if the end of the deque is less than the current element, delete the current element. Then we enqueue the element into the end of the deque. If the size of the deque is greater than the k, we remove element from the front. 

Code (Java):

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        
        Deque<Integer> deque = new LinkedList<Integer>();
        int[] result = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            
            deque.addLast(i);
            
            // Remove if the size of the deque is greater than k
            if (i - deque.getFirst() + 1 > k) {
                deque.removeFirst();
            }
            
            // Add into the result
            if (i + 1 >= k) {
                result[i + 1 - k] = nums[deque.getFirst()];
            }
        }
        
        return result;
    }
}

Summary:
Note that for a deque, first is the left end and Last is the right end. 
The numbers in the deque is actually in reversed sorted order (large first) from front to end.
[ 1 largest, 2nd largest, 3rd largest ...                                 ]
front                                                                                     end

Update on 2/2/2021:

public class Solution {
    /**
     * @param nums: A list of integers.
     * @param k: An integer
     * @return: The maximum number inside the window at each moving.
     */
    public List<Integer> maxSlidingWindow(int[] nums, int k) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        
        if (nums == null || nums.length == 0 || k > nums.length) {
            return ans; 
        }
        
        // deque is a mono-deceasing queue
        // |               |
        // first           last
        // hi              lo
        Deque<Integer> deque = new LinkedList<>();
        
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            
            // add the nums[i] into the last
            deque.offerLast(i);
            
            if (i + 1 - k >= 0) {
                // poll from the first
                if (i - deque.peekFirst() + 1 > k) {
                    deque.pollFirst();
                }
                
                ans.add(nums[deque.peekFirst()]);
            }
        }
        
        return ans;
    }
}