@TWiStErRob@fentoyal I have the same doubt about monotonicity: in your MonoQueue, if you push 5,4,3,2,1 and then check for max and pop you'll get 5,4,3,2,1. How is this monotone (increasing)?
In other words, what is the internal invariant of your data structure? I'm confused by the fact that if you had something like <3,1>,<-1,1> you'd only delete the -1 when pushing a new value bigger than -1.
@JayS03 It might be faster in certain cases but the interviewer will ask you to optimize the code to O(n). Otherwise, a O(nk) solution is meaningless because it's trivial nested for loop and everyone can finish that in 5-10 mins.
Besides, how do you get this conclusion that non-deque solution is faster than deque solution in average? Just because your code beats 99% on OJ? Your code running fast on Leetcode OJ doesn't mean your algorithm will faster than others. Only 18 cases are tested in this problem. When K is larger, this O(nk) will sure slower than Deque solution.
For solution 2: we can use max_heap to get the maximum element of N numbers, and each time we insert a new element, it will take o(logN) time.
There are one difference in this problem:
We need the maximum element under the window of size k, so we need to remove a[i-k] in time, but it is pretty hard to imply by a priority_queue.
----To solve this problem, we decide not to remove the element directly....
Since we need to get the maximum element at each position and the maximum element lies on the top of the priority_queue, before saving this value in our res, we have to check wether it's out of the range k first.