May 11, 2016
Study two blogs. The first one is written in Chinese, link is
here. And the second one is
here.
Read the blog, link is
here.
Julia, please write down your C# practice:
Question and Answer:
1. How long do you study the problem? What do you learn?
Julia spent over 30 minutes on this question. And she learns that deque is excellent data structure to achieve optimal time complexity and complete the task.
2. Can you tell the concrete the example and show how to solve the problem?
Just think like a greedy algorithm. Make the special data structure like Java
Deque data structure, every node is added to the deque once and also removed once. Keep the deque as small as possible, in other words, if the element cannot be the maximum of sliding window, then it should be removed from deque right away.
So, time complexity is O(N).
Also, make it greedy, inside the deque, all elements are sorted by descending order from left to right.
For example, windows size with 4, [1, 3, -1, 2], no matter what next numbers are, 1 and -1 are never going to be a maximal as the window moving. The queue should like [3,2].
So, to maintain the queue in order.
add node in queue from right side only; but remove nodes from both end, just before a node is added.
3. Time complexity analysis:
For those solutions - you can come out:
A. Use heap, or other solutions, time complexity can up to O(nlogn).
w - window size
n - array size
Building a heap, time complexity O(wlogW)
...
so, if w<<n, close to O(n), but if w = 3/n or 4/n, the running time goes up to O(nlogn).
B. ?
4. Learn Java Dequeue class, and C# linkedList:
API:
First:
getFirst
RemoveFirst
Last:
addLast
getLast
removeLast
isEmpty
