Maximum of Each Length-k Window in an Integer Array
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given an integer array `nums` and a window length `k`, slide a window of exactly `k` consecutive elements from the left end of the array to the right end, one position at a time. Return the maximum value inside the window at each position, in order from left to right.
### Function Signature
```python
def window_maxima(nums: list[int], k: int) -> list[int]:
```
### Rules
- The window that starts at index `i` covers `nums[i]` through `nums[i + k - 1]`.
- The output has exactly `len(nums) - k + 1` values; the value at index `i` is the maximum of the window that starts at index `i`.
- Equal values are fine: the output holds values, not positions.
### Constraints
- `1 <= len(nums) <= 10^5`
- `1 <= k <= len(nums)`
- `-10^9 <= nums[i] <= 10^9`, so every value fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: nums = [4, 2, 12, 3, 8, 1, 7], k = 3
Output: [12, 12, 12, 8, 8]
```
The windows are `[4, 2, 12]`, `[2, 12, 3]`, `[12, 3, 8]`, `[3, 8, 1]` and `[8, 1, 7]`.
**Example 2**
```text
Input: nums = [5, -1, -3, 2], k = 1
Output: [5, -1, -3, 2]
```
Each window holds one element, so the output equals the input.
**Example 3**
```text
Input: nums = [-2, -5, -1], k = 3
Output: [-1]
```
There is a single window, the whole array.
Overview: Given an integer array and a window length k, return the maximum value of every contiguous window of length k as the window slides from left to right. The problem tests efficient maintenance of a moving window on arrays of up to 100,000 elements, where rescanning each window is too slow.