Find the Maximums in a Sliding Window

Problem: Given an array of integers and a window that has a size w, slide the window from the left side of the array to the right side, report the maximums in the sliding window during the sliding. For example, a[] = {3,1,5,2,1,4,-3, -2 , 6} and the w = 3. Then at the very beginning, we have [3,1,5] in the sliding window and then the maximum in the window is 5. If we slide the window one step towards the right, we have [1,5,2] in the sliding window and the maximum in the window is still 5. You need to get all these maximums. For this example, the maximum array is {5,5,5,4,4,4,6}.

Solution:  It is easy to know naive approaches will take O(wN), since after each sliding operation, we need O(w) time to find the maximum. To improve, you can use skip list. Basically, you have a sorted linked list to represent the integers in the window. Then you build skip list on top of it. For every slide operation, we need to do an insertion and a deletion. Therefore, the complexity will be O(Nlogw). However, a smarter solution from www.leetcode.com can achieve O(N). The details are as follow:

• Have a double-ended queue (which you can both manipulate the head and the tail. For initialization, add the indices of the first w integers to the queue. While adding indices, we must guarantee the integers to which those indices in the queue point keep a descending order. Therefore, if the index to be added points to an integer that is bigger than some integers to which some indices already in the queue point, we need to remove all "those" indices first.   For the example we showed previously, a[] = {3,1,5,2,1,4,-3, -2 , 6},  after adding the first integer, the state of the queue will be [0], which means a[0] is in the queue; After adding the second integer,   the state of the queue will be [0,1], which means a[0], a[1] are in the queue. Since a[0] > a[1], this guarantee a valid descending order. However, when adding the third integer, we need to pop put both "0" and "1", since a[2] is bigger than either a[0] or a[1]. Then after adding the third integer,   the state of the queue will be [2], which means only a[2] is in the queue.
• Since it is a sliding window, we also need to retire indices that point to the integers which are out of the window. We can do this by checking the indices in the queue and the current location of the window. If some index is out of bound, we need to remove them.
• The size of the queue will always not be bigger than w. For every integer in a[], it will be inserted in the queue and deleted from the queue for at most once. Therefore, the complexity is O(N). 

 You can find the code for this algorithm in  www.leetcode.com.