Sliding Window Maximum with Monotonic Deque
Maintain a decreasing deque of indices to answer maximum-in-window queries in O(1) per element, solving the sliding-window-maximum problem in O(n).
Sliding Window Maximum Problem
The Sliding Window Maximum problem (LeetCode 239) gives an array and a window size k. As the window slides from left to right one position at a time, output the maximum element in each window. A brute-force approach computes the max of each k-element window in O(k) — giving O(nk) total, which is too slow for large k.
The monotonic deque (double-ended queue) solution achieves O(n) overall by maintaining a decreasing deque of indices. The front always holds the index of the current window's maximum, providing O(1) max queries while allowing both front and back operations.
from collections import deque
# Brute force O(nk) for comparison
def sliding_max_brute(nums, k):
return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print('Input:', nums, 'k=', k)
print('Expected: [3, 3, 5, 5, 6, 7]')
print('Brute: ', sliding_max_brute(nums, k))Monotonic Deque: The Key Idea
Maintain a monotonic decreasing deque that stores indices (not values). The invariant: nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[-1]]. Before adding index i:
- Remove expired indices from the front: if
deque[0] <= i - k, the index has left the window. - Remove smaller indices from the back: while
nums[deque[-1]] <= nums[i], those indices can never be the max of any future window (they are to the left and smaller), so discard them.
After these operations, push i to the back. The front always gives the maximum of the current window.
from collections import deque
def sliding_window_max(nums, k):
dq = deque() # stores indices; values are decreasing
result = []
for i, n in enumerate(nums):
# 1. Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# 2. Remove indices with smaller values from the back
while dq and nums[dq[-1]] <= n:
dq.pop()
dq.append(i)
# 3. Record max when first full window is complete
if i >= k - 1:
result.append(nums[dq[0]]) # front = max of current window
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_window_max(nums, 3)) # [3, 3, 5, 5, 6, 7]All lessons in this course
- Monotonic Stack: Increasing vs Decreasing
- Largest Rectangle in Histogram
- Sliding Window Maximum with Monotonic Deque
- Trapping Rain Water: Stack and Two-Pointer