Sliding Window Maximum

Jump Game II

Largest Rectangle in Histogram

Return the maximum of every contiguous window of size k.

You are given an array of integers `nums` and a window size `k`. The window of size `k` slides from the very left of the array to the very right, moving one position at a time. You can only see the `k` numbers inside the window.

Return an array of the maximum value in each window.

## Example
```
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
```

**Constraints**
- `1 <= nums.length <= 10^5`
- `-10^4 <= nums[i] <= 10^4`
- `1 <= k <= nums.length`

**Follow-up**
Could you solve it in `O(n)` time with `O(k)` extra space, and explain why a plain max-heap approach falls short of that bound?

- A window of `k` consecutive elements slides one step at a time across `nums`.
- For each position of the window we report its maximum.
- A length `n` array with window `k` yields `n - k + 1` answers.

Understanding the Problem

- Recomputing the max of every window from scratch is `O(n * k)`.
- For large inputs that is too slow, so we want each element processed a constant number of times.
- The trick: maintain a structure that gives the current window's max in `O(1)`.

Why Naive Is Too Slow

- Store indices in a deque whose corresponding values are **decreasing**.
- Before adding a new index, pop smaller values from the back: they can never be the max while the newcomer is around.
- The front of the deque is therefore always the index of the current window's maximum.

A Monotonic Deque of Indices

- The front index is stale once it falls outside `[i - k + 1, i]`.
- Pop it from the front when `dq[0] <= i - k`.
- Once we have seen at least `k` elements (`i >= k - 1`), record `nums[dq[0]]`.

Evicting Indices That Left the Window

- Time: `O(n)` since every index is added and removed from the deque at most once.
- Space: `O(k)` for the deque plus `O(n)` for the output.