Sliding window maximum over an array and a stream

Two forms of the same problem: the maximum of every window of k consecutive numbers in an array, and a stream structure that reports the maximum of the last k numbers inserted. Expect to start simple and improve.

Part 1: array version

max_sliding_window(nums: list[int], k: int) -> list[int]

max_sliding_window([2, 7, 3, 1, 5, 4], 3)  ->  [7, 7, 5, 5]

Part 2: stream version

Unless you agree on a different interface with the interviewer, assume:

SlidingWindow(k), put(number: int) -> None, get_max() -> int — the largest of the last k numbers put, or of all of them while fewer than k have been put.

w = SlidingWindow(2)
put(5); get_max()  ->  5
put(1); get_max()  ->  5
put(3); get_max()  ->  3     # window is now 1, 3
put(8); get_max()  ->  8

Then improve it in steps: a basic version with its complexity; space reduced to O(k); a comparison of arrays, hash maps, linked lists and heaps for this job; finally the monotonic deque.

Constraints

Up to 10^5 numbers; values may be negative or repeat; k is fixed.

Clarifying questions

What does get_max return before k numbers have been put, and when nothing has been put?
Can numbers repeat or be negative?
How often is get_max called compared with put?

What a strong answer covers

The baseline: store everything and scan the last k, O(k) per get_max; then a circular buffer of size k for O(k) space.
What each structure costs to add the newest number, drop the oldest and find the largest, and why few do all three well (a heap needs lazy deletion of expired items).
The monotonic deque: keep indices of decreasing values; pop smaller values from the back on insert, pop expired indices from the front; the front is the maximum.
Amortized O(1) per operation, O(k) space, and why each element is pushed and popped at most once.
Correct handling of duplicates (pop only strictly smaller values, or track indices).

Follow-ups

Also support get_min() in O(1).
The window is time-based: the maximum of the last 60 seconds.
Many threads call put and get_max. How do you keep it correct?
Return the median of the window instead.