PYTHON
Implementing a Sliding Window Maximum using Deque
Learn to efficiently find the maximum element within every sliding window of a fixed size in a list using Python's `collections.deque` data structure.
from collections import deque
def sliding_window_maximum(nums, k):
if not nums or k <= 0:
return []
# deque stores indices of elements, maintaining them in decreasing order
# for elements within the current window.
dq = deque()
result = []
for i in range(len(nums)):
# Remove elements from the front of the deque if they are out of the current window
if dq and dq[0] == i - k:
dq.popleft()
# Remove elements from the back of the deque that are smaller than the current element
# because they can never be the maximum in any future window that includes the current element
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
# Add current element's index to the back of the deque
dq.append(i)
# Once the window is fully formed (i + 1 >= k), the front of the deque holds the maximum element's index
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Example usage:
data = [1, 3, -1, -3, 5, 3, 6, 7]
window_size = 3
max_values = sliding_window_maximum(data, window_size)
# Expected output: [3, 3, 5, 5, 6, 7]
# print(f"Array: {data}, Window Size: {window_size}")
# print(f"Sliding Window Maximums: {max_values}")
How it works: This snippet demonstrates how to use `collections.deque` to find the maximum element in every sliding window of a fixed size `k`. The deque stores indices of elements in decreasing order of their values. When iterating through the array, elements outside the current window are removed from the front. Elements smaller than the current element are removed from the back because they can no longer be the maximum. The element at the front of the deque is always the maximum for the current window, making this an efficient O(N) solution.