Optimize a sliding window problem using deque

Keep only candidates that can still win

For a fixed-size window maximum, keep indices in a deque whose values are decreasing from front to back. Before processing index i, remove a front index outside the window. Then pop tail indices with values less than or equal to the new value because the new index is later and at least as good for every future overlapping window. Push i; once the first full window ends at i, the front holds its maximum.

Each index enters once and leaves once, giving O(n) time and O(k) space for window size k, compared with O(nk) repeated scans. For minimum, reverse the comparison. Test k = 1, k = n, duplicate values, increasing and decreasing arrays, and invalid k if the API accepts it. Store indices, not just values, because expiration depends on position. If the window is variable-sized, clarify the predicate: a deque helps only when the maintained extremum is the bottleneck.