4 ms·
A Monotone Priority Queue is neither sufficient nor needed to solve this problem (as it does not give a linear time solution). Instead the proper solution just
by poikniok 9y ago
A Monotone Priority Queue is neither sufficient nor needed to solve this problem (as it does not give a linear time solution). Instead the proper solution just needs a deque, see http://techieme.in/maximum-element-sliding-window/ http://techieme.in/maximum-element-sliding-window/.
So yes as you can see knowing algorithms is important, as if you don't you will attempt to use an overly complicated data structure to come up with a suboptimal solution.
- wuch 9y agoThe solution using double ended queue is often referred to as monotonic queue, because queue content will be monotonic sequence.
- jeremysalwen 9y agoThe OP referred to a "Monotone Priority Queue" which seems to be something different: https://en.wikipedia.org/wiki/Monotone_priority_queue https://en.wikipedia.org/wiki/Monotone_priority_queue.