The maximum of every window of k values in O(n): a deque whose values decrease, so its front is always the answer.
This interactive visualization needs JavaScript.