Design and Implement a Sliding Window Maximum API
Design a bounded stateful maximum API, implement the O(k)-query baseline, and then optimize it without changing its public contract.
Design and implement an in-memory `SlidingWindow` object constructed with a positive window size `k`. It exposes `put(number)` to accept one signed 32-bit integer and return no value, and `getMax()` to return the maximum among the most recent `k` accepted values.
For this exercise, assume that before `k` values have been accepted, `getMax()` uses every value seen so far; before the first `put`, `getMax()` reports an explicit empty-window error. Each successful `put` is immediately visible to later calls.
One instance owns one window in one process, and baseline calls are single-threaded. Resizing `k`, removing arbitrary values, persistence, networking, and concurrency are outside the baseline scope. First implement a clear baseline with O(k) memory, amortized O(1) `put`, and O(k) `getMax`.
Then explain how to preserve the same public API while making `getMax` O(1) and keeping `put` amortized O(1) with O(k) memory. Compare the relevant tradeoffs of arrays or ring buffers, linked lists, hash maps, heaps, and a monotonic deque.