219. Sliding Window Maximum
A window of fixed width k slides across an integer array nums, one position at a time, starting flush with the left edge and stopping flush with the right. At each stop you can see exactly k consecutive elements.
Given nums and k, return an array containing the maximum of every window, ordered from the leftmost window to the rightmost. For an array of length n there are n − k + 1 windows.
Recomputing each maximum from scratch is easy but slow. The real challenge: as the window moves, one element enters and one leaves — can you maintain the maximum in amortized O(1) per step?
Example 1:
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]; their maxima are 3, 3, 5, 5, 6, 7.
Example 2:
Input: nums = [7, 2, 4], k = 2
Output: [7, 4]
Explanation: The windows are [7,2] and [2,4], with maxima 7 and 4.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
- 1 ≤ k ≤ nums.length
Hints:
When a new element enters the window, every smaller element already inside can never be the maximum again — the newcomer outlives them and beats them. What does that let you throw away?
Keep a deque of indices whose values are strictly decreasing. Pop smaller values from the back before pushing a new index; pop the front when it slides out of the window. The front is always the current maximum, and every index enters and leaves the deque at most once — amortized O(1) per step.
A max-heap of (value, index) pairs also works: lazily discard heap tops whose index has left the window. That's O(n log n) — fine, but the deque beats it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Expected output: [3, 3, 5, 5, 6, 7]