11 Dec 2011
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. 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]
Ok, the most obvious solution is to loop each window, which takes O(nw).
Of course, there is a better solution. Let's observe:
Let's say we have:
5 2 1 3 4 9, and w is 3
The windows are:
[5 2 1] 3 4 9 5 [2 1 3] 4 9 5 2 [1 3 4] 9 5 2 1 [3 4 9]
The first and second windows are highly related. As the window shifts, it removes one element and add another. However, as long as the maximum is not removed, we do not care.
And the solution seems to emerge. We have a pointer on the maximum element in the window. After we shift the window, we do the following:
And we have to delete element from heap, as the window shifts. So, we need to track indices of elements in a heap. (So complicated)
The best solution we've got so far takes O(n log w). It's not good enough. Let's try to find O(n). The worst case is shown as follows:
6 5 4 3 2 1
We have to update the pointer every time the window shifts.
Basically, we need a data structure that:
Ok, I give up. Let's look at Leetcode.com.
It uses double-ended queue. The queue is kept sorted at all time in a very smart way.
The maximum index is in the front, the minimum index is in the back of the queue, and the queue stores indices.
When the window shifts, we:
This means that some elements, which are not in the windows, can still be in the queue. But they are not in the front or the back. There are 2 observations here.
We do not remove the element immediately when it is out of the window. We only need remove it when it's in the front.
Let's see this example:
[5 1 3] 4
We don't have to keep 1 because 3 is always a better choice. And when we shift the window, we don't have to keep 3 because 4 is always a better choice.
That's why we just remove all lesser elements from the back of the queue and add the new element at the back.
That is a very very smart trick. Each element is added and removed at most once, and there is no loop over the queue. Therefore, the time complexity is O(n).
That is very very smart!