Sliding Window Maximum
A problem which involves finding the maximum element in every subarray of size k.
Visualization
Details
Analogy
Imagine you are looking at a long train through a small window that only lets you see three carriages at a time. As the train moves, your window 'slides' along. For each position of your window, you need to report the height of the tallest carriage you can currently see. The algorithm provides a fast way to do this without re-scanning all visible carriages every time the train moves one step.
Purpose
To efficiently find the maximum value in all contiguous subarrays of a fixed size 'k' within a larger array.
Use Cases
Used in data streaming applications to find maximums over a time period, financial analysis for tracking moving averages or maximums, and in signal processing.
Algorithm Steps
create empty deque and result array
for i = 0 to n-1:
remove indices outside window from front
while deque not empty and arr[deque.back] < arr[i]:
remove from back
add i to deque back
if i >= k-1:
append arr[deque.front] to result
return result
Explanation
What's Happening?
Initial array, window size k=3.
Code Implementation
from collections import deque
def max_sliding_window(nums, k):
result = []
dq = deque()
for i, n in enumerate(nums):
if dq and dq[0] == i - k:
dq.popleft()
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result