Introduction
This time Julia likes to go over Leetcode discussion on the algorithm, and then need to write down most important part - the analysis of using deque, the idea to prune the queue to make it minimum.
Algorithm talk
Read some discussions, take some notes for good comment:
The link is here.
We scan the array from 0 to n-1, keep "promising" elements in the deque. The algorithm is amortized O(n) as each element is put and polled once.
At each i, we keep "promising" elements, which are potentially max number in window [i-(k-1), i] or any subsequent window. This means if an element in the deque and it is out of i-(k-1), we discard them. We just need to poll from the head, as we are using a deque and elements are ordered as the sequence in the array.
Now only those elements within [i-(k-1),i] are in the deque. We then discard elements smaller than a[i] from the tail. This is because if a[x] < a[i] and x < i, then a[x] has no chance to be the "max" in [i-(k-1), i], or any other subsequent window: a[i] would always be a better candidate.
As a result elements in the deque are ordered in both sequence in array and their value. At each step the head of the deque is the max
element in [i-(k-1),i].
Another discussion link is here.
Keep indexes of good candidates in deque d. The indexes in d are from the current window, they're increasing, and their corresponding nums are decreasing. Then the first deque element is the index of the largest window value.
For each index i:
Pop (from the end) indexes of smaller elements (they'll be useless).
Append the current index.
Pop (from the front) the index i - k, if it's still in the deque (it falls out of the window).
If our window has reached size k, append the current window maximum to the output.
Follow up
June 29, 2017
Work on a solution using SortedSet, C# code is here.
No comments:
Post a Comment