Sliding window maximum with a monotonic deque
Each index enters and leaves the deque at most once, so this is O(n) however big k is.
A Queue hands elements out in arrival order (first in, first out); a Deque works at both ends, so it can also be a stack (last in, first out). ArrayDeque, a circular array, is the fastest general implementation of both and replaces Stack and, for queues, LinkedList.
Change the code and press Run (Ctrl+Enter). Try to predict the output first, then break it on purpose and read the error. Your edits are saved and match the lesson page.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Simulate a printer queue: jobs "report", "photo", "invoice" arrive; print them in arrival order using an ArrayDeque as a queue, printing "printing <job>" for each.
Reverse the words of "java is fun" using an ArrayDeque as a stack.
Implement BFS on this graph and print the visiting order from node 0: edges 0-1, 0-2, 1-3, 2-3, 3-4 (an adjacency list of List<List<Integer>>).
Explain it without notes
What is the difference between offer/poll/peek and add/remove/element?
How does ArrayDeque achieve O(1) operations at both ends?
Why should you use ArrayDeque instead of Stack and LinkedList?
Explain the monotonic deque technique for sliding window maximum and its complexity.
Expected output
window max (k=3): [3, 3, 5, 5, 6, 7]
window max (k=1): [1, 3, -1, -3, 5, 3, 6, 7]
window max (k=8): [7]