August 7, 2015
周日玩这个算法, 看到Javascript Array模拟Deque, 非常喜欢, 想用C#数组也模拟; 看有什么新的经历. 试了四五种方法, 花时间研究C# SortedList class. Try to get some workout on the C# programming practice.
我的体会是代码写得太少, 要多读不同的代码, 多调试, 开阔对一个问题思考的思路和深度, 准确度, 实现能力.
1. Blog to read:
C# code implementation (double ended queue is implemented using C# LinkedList class):
https://github.com/jianminchen/slidingWindowMaximum/blob/master/slidingWindowMaximum1.cs
2. Blog to read
C# code implementation (C# does not have deque class, so using C# List<int>,
convert Python code implementation to C#, time limit exceeded)
Good workout on C# List<int>, and also, experience different style on removing head element if out of sliding window.
https://github.com/jianminchen/slidingWindowMaximum/blob/master/slidingWindowMaximu2.cs
3. Blog to read
Method A: naive solution, time complexity O(nw)
Method B: using Self-Balancing Tree (Time complexity: O(nk), need to write c# code)
4. blog:
http://n00tc0d3r.blogspot.ca/2013/04/sliding-window-maximum.html
Good comment about Deque:
We can use a Deque which allow insertions/deletions on both ends. For a Deque implemented by Circular Array/Bufferor Double Linked List, the basic insert/delete operations run in constant time.
discussion of using heap:
The first thought might be heap.
By maintaining a heap for all numbers in the window can give us a O(nlogw)-time solution, where
- building up a heap for initial window takes time O(wlogw)
- when window moves to the next number, each insertion and deletion take time O(logw) and there are n-w moves in total.
- after updating the heap, findMax only takes time O(1) since we know the top of heap is the largest.
So, if w << n, the performance of this solution is good, close to O(n); but if w is not that small, say w = n/3 or n/4, the running time goes up to O(nlogn).
5. blog:
https://github.com/haoel/leetcode/commit/74d83796aa48cc55d7995b1f9e61db40759204bb
using C++ multiset in the above solution, so try to convert it to C# class using SortedList
https://github.com/jianminchen/slidingWindowMaximum/blob/master/slidingWindowMaximu5.cs
6. blog:
http://www.mamicode.com/info-detail-927510.html
convert Java Script code to C#; I spent over 12 months to try to be expert on Java Script, so much fun to read the Java Script code again, and enjoyed the blog about the analysis.
Others:
https://github.com/jianminchen/slidingWindowMaximum/blob/master/slidingWindowMaximu5.cs