Question:
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[i]
http://leetcode.com/2011/01/sliding-window-maximum.html
////////////
// Option A: Using MaxQueue
//
// What is max queue, similar to max stack
private static class MaxQueue
{
private Queue<Integer> queue = new LinkedList<>();
private Stack<Integer> max = new Stack<>();
void offer(Integer t)
{
if (t == null)
return;
queue.offer(t);
if (max.empty() || t >= max.peek())
max.push(t);
}
Integer poll()
{
if (queue.isEmpty())
return null;
Integer t = queue.poll();
if (t >= max.peek())
max.pop();
return t;
}
Integer max()
{
if (max.empty())
return null;
return max.peek();
}
}
// Time: O(n)
// Space: O(n + w)
public int[] slidingWindowMax(int[] A, int w)
{
// Assumptions:
// A not null, not empty, length must >= w
// Init MaxQueue
MaxQueue maxQueue= new MaxQueue();
for (int i = 0 ; i < w ; i ++)
{
maxQueue.offer(A[i]);
}
// Result
int[] B = new int[A.length - w + 1];
B[0] = maxQueue.max();
for (int i = w ; i < A.length ; i ++)
{
maxQueue.poll();
maxQueue.offer(A[i]);
B[i - w + 1] = maxQueue.max();
}
return B;
}
/////////////////
// Option B: Dequeue
//
// It has a better option without using extra stack.
//
// Time: O(n)
// Space: O(n)
public int[] slidingWindowMax(int[] A, int w)
{
// Deque
// See //
// [end ... head]
// Order : >>
// Every time push new element into end, still keep the order
//
Deque<Integer> queue = new LinkedList<>();
// Init deque
for (int i = 0 ; i < w ; i ++)
{
offer(queue, A[i]);
}
// Result
int[] B = new int[A.length - w + 1];
B[0] = max(queue);
for (int i = w ; i < A.length ; i ++)
{
queue.offer(A[i]);
B[i - w + 1] = max(queue);
}
return B;
}
private void offer(Deque<Integer> queue, int t)
{
while (!queue.isEmpty() && queue.peekLast() <= t)
{
queue.pollLast();
}
queue.offerLast(t);
}
private void max(Dequeue<Integer> queue)
{
return queue.peekFirst();
}