LeetCode 239 - Sliding Window Maximum

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example: The array is [1 3 -1 -3 5 3 6 7], and w is 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

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[]

Solution

To get maximal of current window, it can take O(w) or O(logw) time. But we also need to keep track of the maximals as window sliding from left to right.

The first thought might be heap.

By maintaining a heap for all numbers in the window can give us a O(nlogw)-time solution, where

• building up a heap for initial window takes time O(wlogw)
• when window moves to the next number, each insertion and deletion take time O(logw) and there are n-w moves in total.
• after updating the heap, findMax only takes time O(1) since we know the top of heap is the largest. 

So, if w << n, the performance of this solution is good, close to O(n); but if w is not that small, say w = n/3 or n/4, the running time goes up to O(nlogn).

All we need is to keep track of the maximals. Do we really need a heap that performs unnecessary sorting for all numbers in the window?
The answer is NO.

We can use a Deque which allow insertions/deletions on both ends. For a Deque implemented by Circular Array/Bufferor Double Linked List, the basic insert/delete operations run in constant time.

Back to the problem.

What shall we keep in the deque?
If we keep all numbers in the window into the queue, each time when we insert a new number and remove a old one, we need to figure out where to insert so as to maintain the numbers in order. That's not easy...

Actually, we do not need to keep all numbers. For example, suppose numbers in a window of size 4 are

[1, 3, -1, 2], ...

Obviously, no matter what next numbers are, 1 and -1 are never going to be a maximal as the window moving. The queue should look like [3, 2] in this case.

So, to maintain the queue in order,

• When moves to a new number, iterate through back of the queue, removes all numbers that are not greater than the new one, and then insert the new one to the back.
• findMax only need to take the first one of the queue.
• To remove a number outside the window, only compare whether the current index is greater than the front of queue. If so, remove it.

By doing these, we guarantee that the first element of the queue is the maximal and all numbers following it are smaller and came later then it. That said, findMax runs in constant time. Noticing that we only insert and delete each number once. Assuming the insert/delete operations of the Deque run in O(1) time, the total running time for this algorithm is O(n) and it takes at most O(w) space!

/*  
  * Given an array of numbers and a sliding window, find out the maximal  
  * number within the window as its moving.  
  * @param nums the array of numbers.  
  * @param window the size of the sliding window.  
  * @return an array of window maximals, i.e. B[i] is the maximal of A[i, i+w).  
  */  
 public int[] windowMax(int[] nums, int window) {  
   int w = (nums.length < window) ? nums.length : window;  
   // A deque allows insertion/deletion on both ends.  
   // Maintain the first as the index of maximal of the window  
   // and elements after it are all smaller and came later than the first.  
   Deque<Integer> que = new ArrayDeque<Integer>();  
   
   // initialize window  
   int i=0;  
   while (i<w) {  
     while (!que.isEmpty() && nums[que.getLast()] <= nums[i]) {  
       que.removeLast();  
     }  
     que.addLast(i++);  
   }  
   
   // sliding window  
   int[] max = new int[nums.length - w + 1];  
   max[i-w] = num[que.getFirst()];  
   while (i<nums.length) {  
     // add new element  
     while (!que.isEmpty() && nums[que.getLast()] <= nums[i]) {  
       que.removeLast();  
     }  
     que.addLast(i);  
     // remove old element if still in que  
     if (!que.isEmpty() && i-w >= que.getFirst()) {  
       que.removeFirst();  
     }  
     // get maximal  
     ++i;  
     max[i-w] = num[que.getFirst()];  
   }  
   
   return max;  
 } 

我又重构了下代码：

public int[] slidingMax(int[] A, int w) {
	int n = A.length;
	w = Math.min(n, w);
	int k = n - w + 1;
	int[] max = new int[k];
	Deque<Integer> deq = new ArrayDeque<>();
	for(int i=0; i<n; i++) {
		while(!deq.isEmpty() && A[deq.getLast()] <= A[i]) {
			deq.removeLast();
		}
		deq.addLast(i);
		if(i < w-1) continue;
		while(!deq.isEmpty() && i-w>=deq.getFirst()) {
			deq.removeFirst();
		}
max[i-w+1] = A[deq.getFirst()];
	}
	return max;
}

 

From: http://n00tc0d3r.blogspot.com/2013/04/sliding-window-maximum.html