Return the Maximum of Every Sliding Window

## Problem Given an integer array and a positive window size `k`, return the maximum value in every contiguous window of length `k`, from left to right. ### Function Contract Implement `slidingWindowMaximum(values, k)` and return an integer array of length `len(values) - k + 1`. ### Constraints & Assumptions - `1 <= k <= len(values) <= 200,000`. - Values are signed 32-bit integers. - Duplicate maximum values are allowed. - The target time complexity is `O(n)`. ### Clarifying Questions to Ask - Is `k` ever larger than the array? No. - Should duplicate maxima be preserved in the internal state? Their indices matter until they leave the window. - Is the output ordered by window start? Yes. ```hint Store useful indices in a deque Before adding index `i`, remove smaller or equal values from the back. Remove the front when its index is left of the current window. ``` ### Example ```text values = [1,3,-1,-3,5,3,6,7], k = 3 result = [3,3,5,5,6,7] ``` ### Evaluation Focus - Removes expired indices before reading the current maximum. - Maintains decreasing values in the deque. - Emits a result only after the first full window forms. - Handles `k = 1`, `k = n`, duplicates, and negative values. - Runs in `O(n)` time and `O(k)` space. ### Extensions to Discuss 1. How would you compute both minimum and maximum per window? 2. Why does a heap usually incur an extra logarithmic factor? 3. How could this operate on an unbounded stream?