Sliding Window Maximum
Find the maximum value in each window as it slides through the array using a monotonic deque.
Problem Statement
You are given an array of integers nums, there is a sliding window of size k
which is moving from the very left of the array to the very right. You can only see the k
numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window - an array containing the maximum value for each window position.
How It Works
Key Insight
A monotonic deque maintains indices in decreasing order of their values. When a new element arrives, we remove all smaller elements from the back (they can never be maximum). The front of the deque always contains the index of the maximum element in the current window.
Algorithm Steps
- Iterate through each element in the array
- Remove indices from the front of deque that are outside the current window (i - k + 1)
- Remove indices from the back whose values are less than or equal to current element (maintain monotonic property)
- Add the current index to the back of the deque
- Once window is full (i >= k - 1), the front of deque contains the maximum index - add its value to result