Sliding Window Maximum Problem is Not that Difficult

Three approaches to solving the sliding window maximum problem

Sliding Window Maximum Problem

Problem Statement

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
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

def simple(nums, k):
res = []
length = len(nums)

i = 0
while i < length-k+1:
mx = max(nums[i:i+k])
res.append(mx)
i +=1

return res

Solution 2: Priority Queue

import heapqclass Solution:    def maxSlidingWindow(self, nums, k):
lens = len(nums)
h = []
res = []

for r in range(k):
heapq.heappush(h, (-nums[r],r))
res.append(-h[0][0])


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[0][1] <l or h[0][1] > l+k-1:
heapq.heappop(h)
res.append(-h[0][0])

return res

Solution 3: Monotonic Deque

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[0][1] < r-k+1:
d.popleft()

# 2. a new bigger item comes
while d and nums[r] >= d[0][0]:
d.popleft()

# keep Monotonic
while d and nums[r] > d[-1][0]:
d.pop()

d.append((nums[r],r))
if r >= k-1:
res.append(d[0][0])

return res

Developer in China, AI and machine learning enthusiast

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store