Sliding Window Maximum Problem is Not that Difficult
In this post, we are gonna discuss multiple solutions for sliding window maximum problem.
If you prefer to learn through videos, please have a look at the following video.
You are given an array of integers, 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.
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Window position Max
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Solution 1: Brute Force
Among all solutions, Brute force is the easiest one to understand. It moves sliding windows from left to right and searches the largest value for every window.
O(1) not including the output array
The Brute force solution uses almost no additional space. But it is the least efficient algorithm.
def simple(nums, k):
res = 
length = len(nums)
i = 0
while i < length-k+1:
mx = max(nums[i:i+k])
Solution 2: Priority Queue
To find the greatest or smallest value in a shorter time, a priority queue is usually an good choice to consider.
item = (value, index) pair inside the priority queue.
valueis the priority key to compare
indexis useful to restrict window range
- Fill in
kitems into the heap first
- Add the next item into the heap
- Dequeue the first item if the index of it is out of window range
- Repeat step 2 to 3
Here is the code：
import heapqclass Solution: def maxSlidingWindow(self, nums, k):
lens = len(nums)
h = 
res = 
for r in range(k):
for r in range(k, lens):
l = r-k+1
# window index range: l, l+1, ..., l+k-1
heapq.heappush(h, (-nums[r],r)) while h <l or h > l+k-1:
Solution 3: Monotonic Deque
Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”)
A Monotonic Queue is a data structure that keeps its elements either entirely in non-increasing, or entirely in non-decreasing order.
Monotonic deque has three basic operations:
- Push: add an element into the queue
- Pop: remove an element from either end of the queue
- max: peek the max element in O(1）
Here is the code
from collections import dequeclass Solution: def maxSlidingWindow(self, nums, k):
res = 
d = deque()
for r in range(len(nums)):
# remove item outside the window
# 1. if first index in Q(Deque) < i-k+1
if d and d < r-k+1:
# 2. a new bigger item comes
while d and nums[r] >= d:
# keep Monotonic
while d and nums[r] > d[-1]:
if r >= k-1:
If you liked this article, please clap so others can see it. 💚