O(n) time and O(k) memory

Solution 1. Runtime O(n * k)

Brute force solution, every time the window is moved, we can search for the max value in O(k) time.

Solution 2. Runtime O(n * log k) ? 

Similarly with Sliding Window Median, use a max heap data structure;

when the size of this max heap is < k, insert the new element in O(log k);

when the size of this max heap is k, get the max value in O(1);

when the size of this max heap is > k, remove the least recent element; 

The question here is to to remove an element that is not the head/root of a heap, it takes O(k) time, not O(log k). 

If the pq is already given the reference to the to-be-deleted element, then it takes O(log k) time; If not, it takes 

the pq O(k) time to find the element first. 

Solution 3. O(n) runtime, O(k) extra space 

Can we do better?  The BCR is O(n) as we need to scan the input array at least once. In solution 2, we reduced the runtime

of getting the max in a window from O(k) to O(log k), assuming we can remove an arbitrary element from a pq in O(log k) time. 

So, applying the BUD optimizations here, we know that finding each max value in O(log k) time is the bottleneck now. 

Can we reduce it to O(1)? 

The double-ended queue is the perfect data structure for this problem. It supports insertion/deletion from the front and back of the queue.

The trick is to find a way such that the largest element in the window would always appear in the front of the queue. 

A natural way to think is to try to maintain the queue size the same as the window size as it is in solution 2. Try to break away from this thought

and try to think outside of the box. Removing redundant elements and storing only elements that need to be considered in the queue is the 

key to acheive an optimal O(n) solution.  有点类似于使用单调栈来获得O(n)时间复杂度的思想.

Observe the following example, say, we have processed [10 5 3] and the new element is 11. Now, we could‘ve emptied the queue without 

considering elements 10, 5, 3, and insert only 11 into the queue. 

From the above analysis, we drive the following alogrithm.

1. Given a new element nums[i], remove all elements that are <= nums[i] from the queue‘ end;

Doing this ensures the head of the deque always stores the index of the largest element of all elements currently stored in the deque.

At any point, the deque stores indices whose corresponding values are in strict descending order.

2. Remove all indices from the head of the deque that is <= (i - k), if an index t is <= (i - k), it means nums[t] is out of the window already.

3. Add the index i of the new element nums[i] to the end of the deque.

4. Read the head of the deque that stores the index of current largest element‘s in current window.

5. Repeat until all elements are scanned.

Runtime analysis: Each index is pushed and poped at most once, so we have a runtime of O(2 * n) -- O(n)

Space: O(k)

Why do we store elements‘ indices instead of their actual values?

Because we need to remove the out of window elements from the head of the deque. Storing the actual value

does not give us this information. Whereas storing the indices let you know if an index is out of window by checking 

if an index is <= i - k, where i is the current index of the new element. 

 1 public class Solution {
 2     public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
 3         ArrayList<Integer> results = new ArrayList<Integer>();
 4         if(nums == null || nums.length == 0 || nums.length < k) {
 5             return results;
 6         }
 7         Deque<Integer> dq = new LinkedList<Integer>();
 8         for(int i = 0; i < k; i++) {
 9             // as long as the current element nums[i] is >= the last element at the 
10             // end of the deque, remove it. nums[i] is in current window, any element
11             // that is <= is redudant and can be removed from consideration.
12             while(dq.isEmpty() == false && nums[i] >= nums[dq.peekLast()]) {
13                 dq.removeLast();
14             }
15             dq.addLast(i);
16         }
17         results.add(nums[dq.peekFirst()]);
18         for(int i = k; i < nums.length; i++) {
19             while(dq.isEmpty() == false && nums[i] >= nums[dq.peekLast()]) {
20                 dq.removeLast();
21             }
22             //since we insert new elements at the end of the dq, any possible
23             //elements that are out of the the current window will be on the 
24             //front of the dq.
25             while(dq.isEmpty() == false && dq.peekFirst() <= i - k) {
26                 dq.removeFirst();
27             }
28             dq.addLast(i);
29             results.add(nums[dq.peekFirst()]);
30         }
31         return results;
32     }
33 }

Related Problems

Sliding Window Median