Leetcode 239: sliding window maximum

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