Sliding Window Maximum
Given an integer array and a window size k, the window slides one position at a time from left to right. Return the maximum of each window position.
- 1 ≤ n ≤ 10^5
- 1 ≤ k ≤ n
- -10^4 ≤ nums[i] ≤ 10^4
- Fixed-size window, but you need its *maximum* in O(1)
- An element smaller than a newer element can never be a window max again
- Deque with indices, monotonic decreasing
Asking, for every element, about the nearest element to its left or right that is larger or smaller is a signal to keep a stack whose values are sorted. Each element is pushed once and popped once, and the moment it is popped you know exactly who its "next greater" is: the element doing the popping.
Maintain a deque of indices whose values are strictly decreasing from front to back. When a new element arrives, pop from the back every index whose value is ≤ the new one (they are dominated), then push the new index. Pop the front if it has fallen out of the window. After the window is full, the front of the deque is the current maximum. Each index enters and leaves once.
- A max-heap with lazy deletion of expired indices gives O(n log n). A sparse table answers each window in O(1) after O(n log n) preprocessing and handles arbitrary ranges.